Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
783
questions
0
votes
0answers
39 views
Is top-down dynamic programming always recursive?
I think top-down dynamic programming is mostly recursive. For instance, solving the rod-cutting problem by this algorithm:
...
0
votes
1answer
56 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
34 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
43 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
38 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
42 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
56 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
35 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
21 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 ...
1
vote
0answers
31 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
44 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
175 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
31 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
170 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
45 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
48 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
52 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, ...
0
votes
1answer
36 views
reference request: solving problems by dynamic programming + 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), k=0,\dots,N-1
$$
given some $x_0$ and ...
0
votes
0answers
27 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
46 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 ...
2
votes
0answers
38 views
Efficient solution to this scheduling problem or integer optimization problem
Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to
$$
P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)}
$$
where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
3
votes
0answers
50 views
Make Change in Linear Time
The question is motivated by this post on StackOverflow.
Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
0
votes
1answer
30 views
Dynamic programming and probability - list of problems
Does anyone have a list of problems where you have to combine dynamic programming with probability?
0
votes
0answers
44 views
Count of different ways to express N as the sum of given numbers
I'm working on a case and I need some help :)
I need to find number of ways and solutions itself to express N as the sum of given numbers.
So, Sum (N) = 600 and the numbers from which I need to get ...
3
votes
1answer
40 views
What's the runtime complexity of this algorithm for breaking up string into words?
I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to ...
0
votes
0answers
19 views
Alter Sankoff's Algorithm to give all optimal solutions
I'm trying to find a way to alter the Sankoff's Algorithm
so it will trace back all the optimal solutions and not only one.
Is it possible?
1
vote
1answer
41 views
Compute sum of edges in paths from source to target node?
Given a directed acyclic graph G = (V,E). Suppose that the vertices are in topological sort, in particular there exist an edge $(u,v) \in E$ if u <v (see the graph below). The weight $w(u,v)$ on ...
2
votes
1answer
83 views
Minimizing flow on a 2D matrix network
I am currently dealing with a problem that I believe to be a network flow related problem, and I am trying to find some similar solved problems to help me formulate my solution. I want to make it ...
0
votes
1answer
65 views
Group testing puzzle
I have a cake with $n$ layers in total. I know that $k$ are vanilla, and at least $n-k$ are not. I dislike all flavors other than vanilla, so I decide to only eat those layers.
I can't tell which ...
0
votes
0answers
89 views
Dividing a array to into k parts using dynamic programming
I am thinking about how to break an array into k parts using DP with the following requirement.
Array A of size n divided into k parts
All elements are positive integers and order is fixed.
The ...
1
vote
1answer
274 views
If P = NP, would dynamic programming be obsolete?
I know that dynamic programming is used to solve in "pseudo-polynomial time" some NP problems, like the knapsack. If P = NP, would it mean that every problem that we solve with dynamic ...
1
vote
0answers
22 views
Resources on Dynamic Programming with Indefinite Recursion
I am trying to explain the value iteration method that is used in reinforcement learning. The method is used to estimate a solution to a recursive equation like:
$ Return(state_t,action_t) = Reward(...
2
votes
1answer
36 views
dynamic programming: longest palindromic subsequence, recurrence relation question
Moving from top left down the column then over to the right column, taking ideas from here: https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/
I want to restate the question at the ...
0
votes
1answer
114 views
How to derive max amount of items from DP table of Knapsack problem?
I have a little bit changed algorithm for 1-0 Knapsack problem.
It calculates max count (which we can put to the knapsack) as well.
I'm using it to find max subset sum which <= target sum. For ...
1
vote
0answers
29 views
Sub-matrix with minimum size of $k$ and minimum sum
We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The ...
1
vote
1answer
42 views
Dynamic programming: Maximize total value
I was trying to solve this problem using dynamic programming.
We have $n$ objects in a row where each object has a value represented with a positive number.
This is encoded with an array $V[1], . . . ,...
1
vote
1answer
47 views
Time Complexity of Memoized Solution
I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
4
votes
0answers
64 views
Number of permutations with satisfactory triangles
We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
1
vote
1answer
91 views
Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own
I had an online round at a company where I was asked this question.
There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$.
Each item has three ...
2
votes
1answer
106 views
What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?
I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it ...
1
vote
2answers
168 views
Longest sequence of dominoes
Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the ...
1
vote
0answers
79 views
0/1 Knapsack problem with minimal cost
so i have this problem where:
I have to accomplish a challenge A with n quests. Each quest gives me:
p points and
needs t time to be done.
The object is to complete the challenge A that needs M ...
1
vote
1answer
47 views
Can the House Robber problem be solved with a Sliding Window solution?
I was reading an article on how to solve sliding window problems and it said:
Fast/Lagging
This one is a little different, but essentially the slow pointer is simply referencing one or two indices ...
1
vote
1answer
65 views
Greedy algorithm for maintaining drugs
Given $n$ drugs such that each drug $d_i$ should maintain in interval
$[c_i,h_i]$.We want to minimize number of containers to maintain
medicines in compatible interval.
My answer is as follows:
I use ...
2
votes
1answer
73 views
Sub-exponential time algorithm to compute playoff chances
There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the ...
0
votes
0answers
19 views
Can the two optimal subproblems of the recurence formula below be reduced to one subproblem given the assumtions stated in the description below
In CLRS (Intro to algorithms 3rd Edition) on page 362, it says eqn(1) :
Lets Assume that you are given the cost of matrix multiplication for $A_{i}..A_{j}$ is $C[i,j]$ .
$C[i,j]$ is the Number of ...
0
votes
0answers
47 views
Counting number of sequences summing to target
This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading:
We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{...
0
votes
1answer
67 views
Maximize 5-independent gifts on a path
Question: Assume there are $n$ distinct gifts on the real line. Their
positions are $\{x_1, ..., x_n\}$ and each of them has an individual
value $p_i$.
Now you can choose a subset of them such that ...
1
vote
1answer
88 views
Dynamic programming for graph splitting
I have a directed graph which has edges between every vertices $i$ and $j$ such
that $i < j$ and the edge is from i->j and every vertex needs to be visited. I need to divide the graph into two ...
