Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
824
questions
0
votes
0answers
27 views
Find set of vertices of max size under some restrictions [duplicate]
I've faced a problem and I don't know what approach I must follow, dynamic programming or greedy method, so here is the question.
Question: Given a directed tree $T=(V,\ E)$. We're required to find a ...
1
vote
0answers
18 views
Something wrong with my recursion definition - Best Possible Combinatorial Sum from a given list of numbers [closed]
I was trying to solve a problem "Write a function bestSum(targetSum, numbers)` that takes in a targetSum and an array of numbers as arguments.
The function should return an array containing the ...
1
vote
1answer
31 views
Minimum steps needed to partially cover a sequence of points on a grid
Problem statement: You are in a 2D grid where you can move in any of the 4 directions, no obstacles. You start at position (0, 0).
We say that you partially cover a point $(x,y)$ if your position has ...
0
votes
0answers
25 views
How does one generate the dimensions of a dynamic programming problem?
I'm doing this problem https://leetcode.com/problems/maximum-alternating-subsequence-sum/ and attempting to change my code to use a matrix/array. I'm unable to figure out what the dimensions are. ...
0
votes
1answer
40 views
Find $k$ numbers that satisfy a condition from a sorted sequence
Suppose given $T= a_1\leq a_2\leq\dots\leq a_n $ that $a_i$ is real
number and given a number $k$. we want to find $k$ triples $x_i\leq y_i\leq z_i\in T$ such that
$$\sum_{i=1}^ k (y_i-x_i)^2$$ ...
1
vote
0answers
32 views
Maximize the sum of weights of covered intervals
Suppose we are given $n$ open intervals $(a_1, b_1), \dots, (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. We are given an integer $k<n$, and we are allowed to choose $k$ ...
7
votes
0answers
295 views
+100
Optimizing a sum of matrix chains
Here's a practically relevant variation on matrix chain problem:
Find optimal way to compute a sum over all weighted paths in a graph, where the weight of each path is the matrix product of edge ...
5
votes
1answer
77 views
A dynamic program to decide whether the solution is in a given range
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
The problem can be ...
3
votes
0answers
101 views
Generalizing Matrix Chain problem: optimal summation in a tree
Matrix Chain Problem can be viewed as the problem of finding the optimal summation order in a path-structured tensor network. How hard is the problem if we extend it to trees?
For instance, take the ...
0
votes
0answers
56 views
Python closest subset sum function
I'm writing a closestSubset(s,A) function that takes an integer s and an array of positive integers A and returns an array consisting of elements of A which add up to s. If there is no subset that ...
2
votes
0answers
27 views
Finding the cost of Hessian-vector product computation?
Suppose we have a composition of functions $F(x)=f_n \circ f_{n-1} \circ \ldots \circ f_1 \circ x$, where $f_i: \mathbb{R}^{d_{i-1}}\to \mathbb{R}^{d_i}$
The Jacobian of $F$, has shape $d_n \times d_0$...
2
votes
1answer
48 views
Knapsack problems with two sums and two sets
For an algorithm homework, I'm asked to give a solution for a knapsack problem. I have in input a list of products. A product is assigned a cost and a number of calories. So I have two sets, one of ...
1
vote
0answers
20 views
Analyzing possibility of different types of solutions for dynamic programming problems
I was analyzing various classic dynamic programming problems:
1. Cut rod problem
Definition: Given a rod of length n inches and a table of prices pi of selling rods of different lengths i = 1, 2, …, ...
0
votes
1answer
27 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
63 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
28 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
42 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
35 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
56 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
101 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
26 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
57 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
80 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
81 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
36 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
19 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
129 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
131 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
42 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
20 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
122 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
65 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
25 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
26 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
47 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
41 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
23 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
64 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
80 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
50 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
50 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
41 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
55 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
68 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
71 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 ...
