# Questions tagged [dynamic-programming]

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

219 questions
Filter by
Sorted by
Tagged with
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)...
134 views

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 ...
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 ...
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 \\$...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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). ...
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 ...
1k views

### Project Euler #82 - path sum: three ways

Project Euler problem 82 asks: Here's my solution: ...
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 ...
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 ...