Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
811
questions
0
votes
1answer
23 views
FPT for Special Matching
In Special Matching, we are given an undirected graph $G$, a function $w:E\rightarrow\mathbb{N}$, and an integer $k$. The objective is to decide whether $G$ contains a matching $M$ of size at least $k$...
0
votes
0answers
23 views
Intuition behind : recursive algorithm takes exponential time [duplicate]
So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
1
vote
0answers
59 views
Maximum money that can be made
Came across the following question. All the answers provided there have used brute force, more or less. My hunch was that it could be solved using dynamic programming or perhaps, network flow ...
1
vote
0answers
24 views
What are some examples of overlapping subproblems that don't have an optimal substructure thereby we cannot solve it using dynamic programming?
I believe problems like quicksort and other divide-and-conquer are problems that have optimal substructure but do no have any overlapping subproblems. I hope I'm correct here. But I'm unable to think ...
1
vote
0answers
32 views
Proof for knapsack with unlimited items
This is the knapsack problem where the items are unlimited. Let $K(w)$ be be the maximum value achievable for the knapsack capacity of $w$, and $w_i$ and $v_i$ are the weight and value of the item $i$....
4
votes
1answer
33 views
Is there a more efficient way to obtain the optimal input sequence in this finite-state system
Context:
Consider $M$ finite state systems with evolution given by:
$$
x^i_{k+1} = f(x_k^i,u_k)
$$
where $x_k^i\in\{1,\dots,X\}$ is the state of system $i\in\{1,\dots,M\}$, $k\geq 0$, and $u_k\in\{1,\...
3
votes
0answers
46 views
Cost of finding optimal elimination order in a planar tensor network?
Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order?
For example, take the following ...
1
vote
2answers
26 views
Getting three numbers from set that combined gives n
I have run into a little problem that I have been pondering about, and can't figure out a good solution for.
Let's say that I have a set of numbers like this one:
...
0
votes
0answers
99 views
Multivariate piecewise linear interpolation
I am looking for a reference to a solution of the multivariate piecewise linear interpolation. I am not quite sure how to generalize a well-known dynamic programming Segmented Least Squares algorithm.
...
0
votes
1answer
23 views
Dynamic program to solve operation over digits
i have faced this problem that i can not solve.
assume i have a number like n. I want to do m operation over each digit.
in each operation every digit is added by one
for example if my number is 1239 ...
2
votes
1answer
56 views
Cover 2 by n binary matrix with submatrices of minimum total size
This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the ...
1
vote
0answers
79 views
Clustering points on a line
Given pixel values $r_1,r_2,\dots,r_n \in \{0,\ldots,255\}$ and $k$, find
$$
\min_{v_1,\ldots,v_k} \sum_{i=1}^n \min_{1 \leq j \leq k} (r_i - v_j)^2.
$$
My attempt: Let $F[L,c]$ be the minimum cost, ...
1
vote
1answer
65 views
How to get the highest score in this game?
I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
1
vote
1answer
31 views
Finding the uniqueness of longest increasing subsequence
I have a problem related to a common dynamic programming problem LIS. I got LIS function that takes arr as an input and returns the ...
1
vote
0answers
18 views
Thought Process for largest Container of Water Problem
There is a common leetcode problem that asks
Given $n$ non-negative integers $a_1, a_2, \dots, a_n$, where each represents a point at coordinate $(i, a_i)$. Then $n$ vertical lines are drawn such ...
0
votes
1answer
127 views
Number of ways to delete edges from an undirected tree such that each subtree has exactly 1 fruit
An undirected tree has $n$ nodes and some nodes contain a fruit. How many ways can we remove edges from the tree such that each sub-tree has exactly one node with fruit in it?
I found this question in ...
-1
votes
1answer
100 views
Dynamic programming to find number of ways to divide string into primes
I am studying for final algorithms exam and saw this question:
Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers >= 2....
-1
votes
1answer
40 views
Write n in terms of multiplication of numbers from A=[1,...,n] such that the total cost of chosen number is maximum
We want to write n in terms of multiplication of numbers from A = [1,...,n] such that the total cost is maximum. The cost of choosing the ith number is cost[i]. ...
1
vote
0answers
18 views
Discounted Optimal Stopping
The model is as followed:
Consider an infinite horizon discounted problem $(0 < γ < 1)$ in which the state space is finite, with $n$ states, and there are only two possible decisions: stop or ...
0
votes
2answers
115 views
LQR optimal control of accumulator via dynamic programming
Let
$$ x_{k+1} = x_k + u_k, \qquad x_0 = 5 $$
where $k \in \{ 0,1,2,3 \}$, define the return function
$$ - \sum_{k=0}^3 \left( x_k^2 + u_k^2 \right) $$
with the following inequality constraints on the ...
1
vote
1answer
59 views
Find if it's possible to partition a set into 3 disjoint sets each with same sum
Question: I came a cross a problem where we have a set of numbers $W= \{x_1, \cdots, x_n\}$ where repetition of numbers is allowed. We would like to find out whether we can find out 3 disoint sets ...
0
votes
0answers
23 views
Minimizing total penalty from trips over all travel days
I would like to discuss with you please the following problem and it's solution.
Setup: We are travelling with the following constraints:
You can only drive in the daytime.
On any given day, you can ...
1
vote
1answer
21 views
Variation on Matrix Chain problem -- compute diagonal only?
How would you get an optimal schedule to solve matrix chain problem where you only need to obtain the diagonal? (assuming the resulting matrix is square)
First computing the matrix product and then ...
2
votes
0answers
45 views
Variation of the gas station problem
Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
1
vote
1answer
53 views
Traversing a directed graph with negative weights
Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
1
vote
1answer
24 views
Given a source and destination, find the path with minimum stress level in a Graph
I faced this problem in a hiring challenge which is now over.
I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
0
votes
0answers
22 views
Finding all k-partitions with additional constraints
The partition problem is a very well known one. To partition an integer array into k equal sum partitions.
My problem is I want to partition them in such a way that the sum of their partitions equals ...
1
vote
0answers
29 views
Longest substring creating palindromic substring in other string
Given two strings $s, t$, I would liketo find a maximal subsequence of $t$ (denoted as $t'$), such that the concatenation of $t'$ with its reverse ($t'_R$), is a palindromic substring of $s$.
I ...
1
vote
1answer
54 views
House Robber DP Algorithm (Not three in a row)
This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from ...
0
votes
1answer
69 views
Is top-down dynamic programming always recursive?
I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm:
...
0
votes
1answer
59 views
Proving existence of an optimal substructure for the DP problem "Sherlock and Cost" from HackerRank
Problem statement from HackerRank ( source: https://www.hackerrank.com/challenges/sherlock-and-cost/problem ) :
In this challenge, you will be given an array $ B $ and must determine an array $ A $ ....
-1
votes
1answer
48 views
Proving existence of an optimal substructure for the DP problem "Equal" from HackerRank
Q: How one would prove the existence of an optimal substructure for the following DP problem "Equal" from HackerRank?
Problem statement:
My attempt:
Let $ A = [ a_1,a_2,...,a_n ] $ be our ...
1
vote
1answer
47 views
Dynamic Programming: What is a subproblem space? Why do we need varying indexes to characterize a subproblem?
In dynamic programming:
1. what is the definition of the space of subproblems? does it have a mathematical definition?
2. why is it necessary to have an arbitrary index for the subproblem to vary?
To ...
1
vote
1answer
39 views
What are the reasons for solution assumptions behind the longest subsequence problem?
All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L[i] be the length of the LIS ending at index i...":
...
0
votes
0answers
49 views
Given a set of integers and target, find all subsets of size k such that sum of elements of each subset equals target
I am trying to solve below problem
Given a set of integers A, and target integer, find all subsets of size k such that sum of elements of subset equals target.
One approach could be enumerating all ...
0
votes
1answer
60 views
speed up straightforward solution using dynamic programming
i recently got onto the following problem: we consider the following array:
A = [2, 3, 6, 1, 6, 4, 12, 24]
we need to count the number of times these two ...
1
vote
1answer
52 views
How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?
I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
0
votes
0answers
35 views
Minimum weight $k-$path cover on a DAG proof verification
Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an
integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
0
votes
0answers
34 views
Is weighted interval scheduling where the weights are the interval lengths simpler/faster
In weighted interval scheduling arbitrary weights are given to the intervals. A clean dynamic programming solution runs in $O(n \log n)$ time.
If the weights of the intervals are their integer lengths,...
0
votes
0answers
57 views
Bin packing problem using bit masking
We have n box and an array of weights, where weight of ith box is given by arr[i]. We have a container which can carry a maximum weight of w. Now we have to find minimum number of containers required ...
1
vote
0answers
267 views
Minimum no of swaps to be done in an array such that, no two adjacent elements are same
Given an array of size n, find minimum number of swaps required, so that no two adjacent elements are equal. For ex-
n = 6, a[] = {1, 1, 5, 2, 5, 5}, answer = 1, ( swap a[0] with a[4] or
a[5] )
n = 8,...
2
votes
0answers
42 views
Constrained/Optimal Topological Order to enhance/reduce the performance/memory usage of other algorithms
I originally posted this question here
Lets assume we have a highly connected directed acyclic graph (DAG, more edges then nodes). Since it is a DAG, we can retrieve a topological order of nodes to ...
0
votes
0answers
283 views
Minimum Number of Refueling Stops with Dynamic Programming
This is a question from Leetcode and I wanted to solve it with Dynamic Programming. upon seeing the solution, I am not able to get the intuition behind the logic. I was able to understand the solution ...
0
votes
0answers
63 views
Minimize the average distance from each cities to the closest hospitals
There are n cities [1, 2, 3, .... n] and k available hospitals. k < n. We need to place hospitals into the cities. How to place these hospitals to minimize the average distance from each cities to ...
0
votes
0answers
18 views
How do I group elements of a list into windows of predefined sizes with minimum cost given longer windows are cost efficient?
You are given a list of days numbered 0 to 365 in the calendar year where you need to be in a hotel. You need to book in advance for the year and need not necessarily be there when you have a booking. ...
2
votes
1answer
70 views
Number of subsequence with k distinct characters
"A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order."
Suppose we have string s="aabca&...
1
vote
3answers
62 views
Greedy Algorithm: Optimal Substructure
I don't have a CS degree but I have recently taken up studying algorithms very seriously.
I have been studying greedy and dynamic programming for days and I come across the below definition a lot, ...
1
vote
1answer
63 views
Solving problems by dynamic programming plus quantization to avoid combinatorial explosion
The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to:
$$ x_{k+1} = f(x_k,u_k) $$
where $k \in \{ 0,\dots,N-1 \} $, ...
0
votes
0answers
33 views
Is correctness implied by an optimality proof?
New to proofs (in the context of analysis of algorithms).
I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + ...
0
votes
1answer
57 views
DAG for contiguous subsequence of maximum sum
I have trouble understanding DAG behind the "contiguous subsequence of maximum sum problem". Let's say I denote by S(i) maximum of sums of contiguous ...
