# Questions tagged [dynamic-programming]

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

619 questions
Filter by
Sorted by
Tagged with
17 views

### Doest sorting accept a dynamic programming solution?

Are there any known / efficient dynamic programming solutions to sorting? I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal ...
42 views
+50

### How can this Line-Breaking algorithm consider spaces as having width different than 1.0?

The Divide & Conquer Algorithm for Line-Breaking described here is given below, both in Python and in Dart (which is similar to Java/C#). Line-breaking is also known as "line wrap", "word wrap", ...
9 views

### Why some website I cannot open? [closed]

I try to open many time this site this link: https://uopeople.influitive.com/users/sign_in however something wrong. This is what it says, This page isn’t workingambassadors.uopeople.edu redirected you ...
19 views

### Knapsack-like problem with profit formula

Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once. The ...
75 views

### 3xN tiling problem with 3x1 vertical and horizontal + 2x2

I know there are a number of different tiling problems and some of them have been discussed here: Number of ways of tiling a 3*N board with 2*1 dominoes problem Domino and Tromino Combined Tiling DP ...
943 views

### DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $max { [v + f(k-1,g-w ), f(k-1,g)] }$ if w <= g and k>0 CCP recurrence relation $min {[1 + f(r,c-v), f(r-1,c)]}$ if v <= c and r>0 I don't ...
24 views

### The average number of dominos

Consider there are $n$ dominos to be placed in a lone (such as "DDDDD", where D is dominos). While placing dominos, they may fall to their right or left, making other dominos in line to fall down. ...
7k views

### Dynamic Programming vs Memoization

I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization. Am I ...
25 views

### Is it possible to find a supersequence of a single array?

In Jeff Erickson's Algorithms textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest oscillating supersequence of an arbitrary ...
37 views

### Implementing Dynamic Programming Solutions

I know there alot of questions on Dynamic Programming and I feel I have a handle on the theory, use the answers from sub problems to answer the current problem, without the redundancy of recursion. ...
81 views

### Dynamic programming problem

our uni is closed because of the COVID-19 and I'm trying to homelearn dynamic programming. In our algorithms book, there is the following problem: (an example problem for dynamic programming) A ...
46 views

### LaTex Text Justification badness penalty

I had been going through dynamic programming concepts and happened to read about text justification problem in which the spaces to the right of the line end are penalized with cubic times the number ...
31 views

### Is there a faster than O(n^2) solution for Box stacking problem?

Is there a faster than O(n^2) solution for the Box stacking problem?
24 views

### How to approach weighted job/interval scheduling problem with 2 machines (dynamic programming)

Given N jobs where every job is represented by the following: Start Time, Finish Time and Value Associated (>= 0) and two machines that can do the jobs, The goal is to find the maximum value subset ...
57 views

### Min-coin change problem with limited coins

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
29 views

### Minimum moves to “stabilize” an array

We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the ...
31 views

### Catching ball - finding the maximum number of caught balls

I'm attempting to solve the following problem: Balls are falling from the sky. We know at which location (on a straight line) will each ball drop, and we know the time (in seconds) at which ...
56 views

### Give an efficient Dynamic programming algorithm that takes strings s,x, and y and decides if s is an interleaving of x and y

I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book. Not a homework You’re consulting for a group of people (who would prefer not to be ...
99 views

### How can I solve this problem using dynamic programming?

I'm stuck in this problem and I would need some help: Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. ...
270 views

181 views

### What is the optimal way to perform GCD chain operation?

Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming. Similarly ...
47 views

### A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...