Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
776
questions
2
votes
0answers
17 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 ...
-1
votes
0answers
26 views
Minimum cost required to cover a line with line segments
We are given a line segment $[1, n]$ with $m$ smaller line segments $[l_{i}, r_{i}]$.
An example being $[1, 4]$ and line segments ${[1,2], [2,3], [3,4]}$. We can cover this using first and third ...
0
votes
0answers
18 views
CSES Question - Tower [closed]
Ques Link: https://cses.fi/problemset/task/1073/
Code Link: https://pastebin.com/S9nzVJVa
In CSES question : Towers, I know it can be solved using sets with greedy approach but I was trying to do ...
0
votes
0answers
33 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
36 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
38 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
34 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, ...
-2
votes
0answers
48 views
An Dynamic Programming algorithm for this problem(Largest Tower)
We have some blocks of the tower(n) with the same Height(each of them has 1 as its Height)
each block has Weight(w) and maximum Tolerable weight(L).each block can withstand a certain weight(L).
if a ...
0
votes
1answer
33 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
22 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
41 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
49 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
24 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
40 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
37 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
40 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
78 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
64 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
85 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
267 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
20 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
34 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
106 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
28 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
39 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
35 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
62 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
57 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
104 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
123 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
72 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
33 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
60 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 ...
0
votes
0answers
30 views
Dynamic Programming, lru-cache, “minimum weight of a number”
I'm struggling with the following problem: The weight of a correct arithmetic expression, consisting only of the strings 1, x, +, is defined as the number of 1s appearing in the expression. Each ...
2
votes
1answer
68 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
43 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
87 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 ...
0
votes
2answers
19 views
Longest common subsequence solution reconstruction during DP is wrong
I've implemented longest common substring in python. I know the usual way to reconstruct the path. But, I am reading my algorithm many times, I don't understand why ...
6
votes
0answers
81 views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
0
votes
1answer
40 views
Finding shortest path for DAG using dynamic programming vs topological sort?
Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the ...
1
vote
1answer
25 views
Sum of products over k-permutations
Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n_1...n_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to ...
3
votes
2answers
168 views
Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$
I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
1
vote
1answer
26 views
What problem is this? Largest sum produced by selecting one number at each index from n lists, with restrictions
Suppose you have an $n\times m$ 2D array consisting of each $n$ rows of $m$ real numbers. What is the sequence of indexes $i_1,i_2...i_m$ such that $\sum_{j=1}^mA[i_j, j]$ is maximized, subject to the ...
3
votes
1answer
75 views
Completing tasks on a graph
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that ...
0
votes
2answers
72 views
Question concerning subset sum problem: split into 3 equal subsets
Task: Given an array $arr[a_1, a_2, \dots, a_n]$ of integers, let $A = \sum\limits _{i\in \{1, 2, \dots, n\}}a_i$. Determine whether it is possible to spit $arr[]$ into 3 subsequences of equal sum, i....
