# Questions tagged [dynamic-programming]

Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

571 questions
Filter by
Sorted by
Tagged with
1k views

### How can I improve my Algorithm?

This is a problem from Interview Street in Dynamic Programming section. https://www.interviewstreet.com/challenges/dashboard/#problem/4f2c2e3780aeb Billboards(20 points) ADZEN is a very ...
2k views

### Maximum Schedulable Set Zero-Lateness Deadline Scheduling

This is a homework problem for my introduction to algorithms course. Recall the scheduling problem from Section 4.2 in which we sought to minimize the maximum lateness. There are $n$ jobs, each ...
826 views

### How to do Fairy Chess problem in O(N^3)?

https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c88e0dec8a Fairy Chess (35 Points) You have a $N \times N$ chess board. An $S$-leaper is a chess piece which can move from ...
3k views

### Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order

I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested ...
169 views

4k views

### Dynamic programming with large number of subproblems

Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street: Grid Walking (Score 50 points) You are situated in an $N$-dimensional grid at ...
669 views

### Problem contest with matrix and DP

I found this problem while I was reading an ACM problem and it is about dynamic programming. The problem says that you have a square matrix $n\times n$ filled with 1's or 0's, like this: \begin{...
713 views

### Micro-optimisation for edit distance computation: is it valid?

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: ...
240 views

1k views

### How to use dynamic programming to solve this?

Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies ...
12k views

### When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
2k views

### Is it possible to use dynamic programming to factor numbers

Let's say I am trying to break all the numbers from 1 to N down into their prime factors. Once I have the factors from 1 to N-1, is there an algorithm to give me the factors of 1 to N using dynamic ...
1k views

### Maximise sum of “non-overlapping” numbers in square array - help with proof

A question was posted on Stack Overflow asking for an algorithm to solve this problem: I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The ...
12k views

### dynamic programming exercise on cutting strings

I have been working on the following problem from this book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves ...
21k views

### Knapsack problem — NP-complete despite dynamic programming solution?

Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right? I have read it is actually an NP-complete problem, though, which ...
15k views

### Deciding on Sub-Problems for Dynamic Programming

I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer....
2k views

### A Case Distinction on Dynamic Programming: Example Needed!

I have been working on dynamic programming for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See ...