Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
571
questions
1
vote
1answer
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 ...
2
votes
1answer
452 views
Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time
Let PARTITION-INTO-THREE-SETS be defined as following:
Input: Positive integers $a_1, ..., a_n$
Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup ...
1
vote
1answer
78 views
Finding optimal multiplication order and optimal binary tree
I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.
Consider the following ...
0
votes
0answers
21 views
Value iteration in MDP - updating each state once per inner loop?
In value iteration algorithm we update the utility of all possible states ("for each state update its new utility").
After we've updated all states we check to see if the delta is smaller than some ...
1
vote
1answer
364 views
What Are the Ideas Behind Variations of the Coin Change Problem?
Problem: given a set of n coins of unique face values, and a value
change, find number of ways of making change for ...
1
vote
0answers
121 views
Is MCTS an appropriate method for this problem size (large action/state space)?
I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t)...
1
vote
1answer
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?
1
vote
0answers
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 ...
2
votes
2answers
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 <...
2
votes
4answers
80 views
1
vote
2answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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/...
12
votes
2answers
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 ...
2
votes
1answer
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
...
2
votes
0answers
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 ...
1
vote
1answer
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...
2
votes
1answer
553 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 ...
0
votes
0answers
132 views
Intuition behind Floyd-Warshall being faster
I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm:
Let $dp[i][j][n]$ denote the shortest path from $...
0
votes
0answers
49 views
What will be an O(n) solution for this?
Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at ...
2
votes
3answers
645 views
Algorithm to find smallest number divisible by N with sum of digits as N
Problem:
Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$.
For example:
$n = 1$, answer is $1$
$n = 10$, answer is $190$
There is some dynamic programming ...
1
vote
1answer
182 views
Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items
For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
0
votes
1answer
44 views
Sum of zero nim sum series
The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\...
1
vote
0answers
76 views
Possible Distribution of coins
We are given a set of $n$ coins with denominations $v_1,v_2,\ldots,v_n$ and a number $x$.
The coins are to be divided between to persons, with the restriction that each person's coins must add up to ...
2
votes
0answers
73 views
Balls in Bins with Pairwise Distance
Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
1
vote
1answer
449 views
Algorithm Design for Linear Programming
I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing.
I am working on the following problem:
Suppose you are consulting ...
1
vote
1answer
363 views
Gerrymandering Problem: Variant on Set Partitioning
I was recently helping a friend with homework from a dynamic programming class, and this was the question:
Given a set of
n
precincts
P1
,...
Pn
, each containing
m
votes, with <...
2
votes
0answers
156 views
Tail recursion can't work with dynamic programming programs
I am doing some exercises on dynamic programming in order to get familar with this concept.
I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
2
votes
1answer
52 views
Making a profit as a high-dimensional store owner?
Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient.
Let's say that I am some business owner with a set of $...
2
votes
3answers
4k 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 ...
1
vote
1answer
160 views
Help writing a dynamic programming algorithm in English
It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party....
0
votes
1answer
61 views
Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids
The question is:
There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path
exists, 1 means the cell is blocked and 2 means there exists gold in
that cell. Task is to start from 0,...
2
votes
1answer
158 views
How to find the number of Binary Search Trees with given number of nodes and leaves?
With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that:
Exactly $1$ leaf node(s) present?
Exactly $2$ leaf nodes present?
I was able to solve the first ...
2
votes
1answer
48 views
longest sub-sequence in both directions
Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.
Example: A = cabca
the sub-sequence S = abc is the ...
2
votes
2answers
56 views
How can I reduce the time of this program
I solved a problem similar to the knapsack problem.
There are two packages with a capacity of $P$ on a production line. We want to put $N$ items in them with the weights $w_1,...w_n$ in a pre-defined ...
2
votes
1answer
419 views
The number of balanced trees with N node and L leaves
An algorithm is requested to calculate all balanced binary trees which can be built with $N$ nodes, having exactly $L$ leaves. A balanced tree is a binary tree in which the difference between the ...
-1
votes
2answers
469 views
How can I write this backtracking algorithm using dynamic programming?
Problem:
There are $n$ points on a map, $p_1,..p_n$. There are two officers located initially at $(0,0)$ coordinate. They want to patrol all of these points with a minimum traveling (each officer ...
1
vote
0answers
253 views
Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))
So this is a question within a bigger question for which I've reduced to this so far:
If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal ...
2
votes
0answers
110 views
Weighted Sorting Algorithm
Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation.
Is there any ...
1
vote
1answer
55 views
Can the compiler convert recursive algorithm into a dynamic programming
So I was going through the idea behind dynamic programming (memoization), and thought of this question.
Can a compiler convert any recursion into a table filling DP solution, of course given the ...
1
vote
1answer
54 views
Optimizing the problem
I have a recurrence relation:
$$f(a,b) = \begin{cases}
1 & (a,b) = (0, 0)\\
1 & (a,b) = (a, 0)\\
0 & (a,b) = (0, b)\\
2a & (a,b) = (a,1)\\
f(a-1,b) + f(a-2, b-1) + f(a-1,b-1)...
0
votes
1answer
180 views
Finding recurrence relations for dynamic programming algorithms
Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by ...
1
vote
2answers
150 views
FInding the combination with the least number of elements from and array of integers, given an integer sum
I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
1answer
136 views
Minimum Number of Integers From a List that Add up to N (Dynamic Programming)
A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically:
Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where ...
0
votes
1answer
37 views
Maximum trailing zeros of the path
Problems:
A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, ...
