Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

Filter by
Sorted by
Tagged with
4
votes
1answer
212 views

NGON (many polygons) on SPOJ

I am trying to solve NGON problem. I am using bottom up dynamic programming here. Recurrence function is: $$\begin{array}{rl} f(a,b) &= f(a-1,b) + f(a-1,b-1)\,a_i +\frac{f(a-1,b-2)\,a_i(a_i-1)...
11
votes
1answer
134 views

Loading Data Warehouse with Dynamic SQL

For a data warehousing project I ran into the following: Custom fields that users can create, modify and delete, that should be loaded into the data warehouse as they are when the ETL happens. On ...
2
votes
1answer
773 views

Determine if subset in int array adds up to a given input integer

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. On similar lines, Partition problem is to determine whether a given ...
4
votes
2answers
663 views

The Three-machine proportionate flow shop problem with unequal machine

As part of an Academic project I wrote the following code, according to the algorithm (verbal). When I checked the rest of the article I notice that the efficiency should be \$O(n^2)\$ and I wrote \$...
4
votes
1answer
399 views

Dynamic programming with Project Euler #18

I just wanted to get an opinion on my dynamic-programming Haskell implementation of the solution to Project Euler problem 18. The Problem: By starting at the top of the triangle below and moving ...
5
votes
2answers
4k views

Optimizing O(m n) solution for longest common subsequence challenge

Given two strings string X of length x1 and string Y of length ...
7
votes
1answer
510 views

Three-machine proportionate flow shop problem with unequal machine

As part of an academic project I wrote a code about dynamic programming that solves the "Three-machine proportionate flow shop problem with unequal machine". In flow shop scheduling it is usually ...
11
votes
3answers
1k views

Optimizing “Herd Sums” problem using dynamic programming

I'm trying to solve a practice problem and all is well except for the last 2 inputs my solution is too slow. Just one loop is slowing it down I think. Herd Sums Execution Time Limit: 2 seconds ...
7
votes
2answers
3k views

Finding alternating sequence in a list of numbers

Please be brutal and treat this as me coding this up for an interview. A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between ...
8
votes
1answer
1k views

Assembly line scheduling

This is solution to the assembly line problem. Here is complete description, which is too big and verbose to re-describe. I apologize for the inconvenience of the hyperlink. Note: I do understand ...
1
vote
1answer
1k views

Knapsack 01 solution

Solution to bounded knapsack 01 problem. Once again comprehensive description is difficult in this space, refer here. Looking for code review. optimizations and best practices. ...
4
votes
2answers
246 views

Returning all the LIS of given array of int

I have this assignment where I'm supposed to code an algorithm for finding the quantity of Longest Increasing Subsequences from an array of (different) integers and print them all. I developed one ...
1
vote
1answer
1k views

MaxSum sub matrix within a matrix

Code review for best practices, optimizations, code cleanup etc. Also requesting verification of the complexity: O(row*row*col). ...
6
votes
2answers
1k views

Box-stacking problem in C++

I have tried to write code of Box stacking problem (mentioned here) in C++ . Kindly give me some views on what mistakes I might have made and how I can improve. It is running for the two inputs I have ...
2
votes
1answer
1k views

Project Euler #82 - path sum: three ways

Project Euler problem 82 asks: Here's my solution: ...
2
votes
1answer
3k views

Jump game in Java

Looking for code review, suggestions for improvement, best practices etc. The problem definiton is Jump Game Given an array start from the first element and reach the last by jumping. The ...
4
votes
2answers
3k views

Project Euler #15 — count possible lattice paths

I'm not a C programmer, just wanted to make a fast solution to the problem. Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 ...
46
votes
2answers
60k views

Dynamic programming knapsack solution

I wrote a solution to the Knapsack problem in Python, using a bottom-up dynamic programming algorithm. It correctly computes the optimal value, given a list of items with values and weights, and a ...
7
votes
4answers
7k views

Python implementation of the longest increasing subsequence

Prompted by this question on Stack Overflow, I wrote an implementation in Python of the longest increasing subsequence problem. In a nutshell, the problem is: given a sequence of numbers, remove the ...