Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
988 questions
2
votes
1
answer
227
views
Knapsack problem with bounded value/cost ratios
Consider an instance of the knapsack problem: there are some $n$ items, each with a value and a cost. We should choose a subset of items with total cost at most $C$, and subject to that, with a ...
- 6,131
1
vote
2
answers
94
views
Counting monotone sequences with strictly increasing XOR differences
I would like to understand the structure of sequences whose consecutive XOR values increase strictly. The problem is as follows.
Let integers $(l,r)$ be given with $1\le l\le r$.
Consider all finite ...
- 11
0
votes
1
answer
136
views
Runtime analysis of Fibonacci series
To compute the $n$th Fibonacci number, a recursive algorithm is as follows:
...
- 167
1
vote
1
answer
136
views
Runtime for the unordered "Errands" problem
Consider the following problem:
Let $G=(V, E)$ be a weighted undirected graph with nonnegative weights. Let $S_1, S_2, \ldots, S_k\subseteq V$ be disjoint subsets representing vertices where you can ...
- 63
0
votes
0
answers
173
views
3-Partitions with same sum problem algorithm
this is the problem statement (3-Partition Problem): Partition a set of integers into three subsets with equal sums.
Input: a sequence of integers $v_1, v_2, ..., v_n$
Output: check if it is possible ...
- 1
1
vote
0
answers
81
views
How can we solve Hitting set instance in runtime $O(2^k)$ using Dynamic Programming, where $k$ is the number of sets?
Suppose we have a hitting set instance $(U, F)$ where $U$ is the universal set and $F$ is the family of subsets of $U$. $F$ has $k$ many sets $=\{f_1, f_2,...,f_k\}$ and $U$ has n many elements. Using ...
- 11
1
vote
0
answers
39
views
Graph labeling through optimization of a quadratic form
Given a simple unlabeled graph $G = (V,E)$ with vertices $V=\{1,\ldots,n\}$, let $L(G)$ a labeled graph obtained by labeling (with distinct labels) the vertices of $G$ through any $l: V \rightarrow V$ ...
- 155
2
votes
1
answer
240
views
Why does Levenshtain Distance take into account DP[i-1][j-1] when computing the minimum, if LCS doesn't when computing the maximum?
In dynamic programming, why does Levenshtein Distance algorithm take into account DP[i - 1][j - 1] when computing the minimum, but Longest Common Subsequence doesn'...
- 171
2
votes
1
answer
320
views
Find path in Directed Acyclic Graph from starting to ending node where each node is connected from an ancestor in the path
I am given a directed acyclic graph and I want to find all paths from a starting node to an ending node such that all child nodes are connected to previous ancestors. I'm not even totally sure how to ...
- 23
0
votes
0
answers
29
views
specific edit distance problem with transposition solution time and space complexity in Python
Find min edit distance given source and target string and costs to insert, del, subsitute, and transpose 2 adjacen character)
reference:
https://en.wikipedia.org/wiki/Damerau%E2%80%...
- 11
2
votes
0
answers
57
views
Asymptotic complexity of knapsack algorithm considering all numbers ∈ Z
In the knapsack problem, we consider numbers ∈ Z+ which gives us a run time of $O(nW)$. To my understanding, this is pseudo-polynomial and the worse case runtime is $O(n*2^{log(w)})$
My question is, ...
- 21
1
vote
0
answers
57
views
Finding negative cycle in a multi/hyper graph?
I have the following problem:
Suppose I have n items and there is an exchange ratio for the items, $K_{ij}$ tells me how many items of type $j$ I will receive for $1$ unit of item $i$.
Question: Is ...
- 796
0
votes
1
answer
115
views
Expressing a mathematical recurrence relation for the coin change problem with one parameter
I've recently begun studying about the dynamic programming paradigm, and came up across two variations of the coin change problem as described below:
Given a set of coin values $C = \{c_1,c_2, ...\}$, ...
- 103
0
votes
0
answers
99
views
Maximizing Edge Sum
So there is this question :
we are given a tree with n nodes. For each node, $i$ we are assigned two values : a $r_i$, that is the right boundary, and a $l_i$, which is the left boundary. We should ...
- 45
0
votes
1
answer
131
views
Most Efficient way to compute array
I ran into a problem while solving this question and I am not sure about the approach of how to find the most efficient approach and time complexity for finding this optimal subsequence for this ...
- 1