Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
987 questions
0
votes
1
answer
115
views
Runtime analysis of Fibonacci series
To compute the $n$th Fibonacci number, a recursive algorithm is as follows:
...
- 163
1
vote
1
answer
129
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
161
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
78
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
32
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
236
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
242
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
28
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
53
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
35
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
106
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
44
views
Is my calculation of the number of functions for 𝐹 ( 𝐴 𝐵 𝐶 , 𝑟 , 𝑘 ) and 𝐺 ( 𝐴 𝐵 𝐶 , 𝑟 , 𝑘 ) correct?
I’m working on a problem involving dynamic programming in graphs. The sub-path (ABC) has vertex weights and edge lengths, and we are tasked with calculating the optimal cost of a (k)-center.
Given (k =...
0
votes
0
answers
96
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 ...
- 35
0
votes
1
answer
109
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
1
vote
1
answer
131
views
Showing Dijkstra's algorithm works for bridge negative edges
Let $G=(V,E)$ a directed graph with weight function $w:E \to R$. let $s \in V$ a vertex s.t it has path to any other vertex in $G$. Suppose that every negative vertex in this graph is bridge edge, ...
- 181