Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# 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
48 views

### Computing number of ways to make change

Given a list $C=[c_1,c_2,\dots,c_k]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total ...
452 views

68 views

### Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?

I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop. Is this reasoning correct or is there more to it?
34 views

### Count paths in matrix that visit each number exactly once [duplicate]

Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$. We want to count the number of paths that start ...
488 views

### Technique for converting recursive algorithm to DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
80 views

### Prooving by Pigeonhole principle

I've been given a question to solve: ...
337 views

### set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
190 views

### Maximize interleaving subsequences two digit arrays/strings

Suppose I have two digit arrays, A and B as follows A = [3,4,5,6] B = [9,8,3] Now, I have ...
43 views

### Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
65 views

### Number of contiguous subsequences summing to a given target

I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$. For ...
58 views

### Multi Knapsack each with different constraints

It seems that there's no end to knapsack variations… here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
85 views

### Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
97 views

### How to find efficiently the minimum modification to avoid close consecutive numbers?

I have an array of sorted numbers: arr = [-0.1, 0.0, 0.5, 0.8, 1.2] I want the difference (dist below) between consecutive ...
88 views

### What is the optimal way to solve the following optimization problem

You are given a function $F$, which can take one or more positive integer operands. Let $L=\{a_1,a_2\ldots a_n\}$. We need to compute the function $F(L)$ using the least number of transformations/...
265 views

### Word factorization in $O(n^2 \log n)$ time

Given two strings $S_1, S_2$, we write $S_1S_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a ...
133 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 ...
30 views

### What are the pros and cons of context-oriented programming (COP)?

I have started reading about COP, but can't really get a grip of it. What I understand is that you use layers to let the software dynmically adapt depending on the context, and this would result in ...
191 views

### How to minimize the average distance between pumps and cities?

There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k...
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 ...