# Questions tagged [dynamic-programming]

Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

607 questions
Filter by
Sorted by
Tagged with
733 views

### Length of longest arithmetic progression in an array

I was reading an article on Longest Arithmetic Progression. The solution given has S(n)=$O(n^2)$. Can't I solve it in $O(1)$ space? To find the three elements, we first fix an element as middle ...
47 views

### Extended stars and bars approach using dynamic programming

If we have an equation with N variables of the form x1 + x2 + x3 +...+ xN with sum S, and upper and lower bounds for each of the N variables, is it possible to find the number of integer solutions (...
285 views

### Is deep learning appropriate to approximate dynamic programming problems?

I have a problem which can be completely solved using dynamic programming, but in a very intractable way (On^4, where n is around 1000). I won't get into the details of the problem since it's a bit ...
149 views

### what is the significance of the word “Sub-problems” in Greedy Method?

With respect to Dynamic Programming we make a statement that : Greedy algorithm have a local choice of the sub-problems whereas Dynamic programming would solve the all sub-problems and then ...
543 views

### Can Tug of war problem be solved by DP or greedy approach?

For problem explanation: https://www.geeksforgeeks.org/tug-of-war/ I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ...
20 views

### How can I solve it (modification of famous robot travelling problem)?

Imagine you have to solve this question (+ you have obstacles, i.e. walls), but you're allowed to move in any of 4 directions (not just 2: down and right). How can you solve it? I'm struggling to ...
22 views

### Marginalise edge weights on graph

I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a ...
585 views

### How can I find worst time complexity for a Regular Expression problem?

I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution? One way is to perhaps use The Master Method for ...
372 views

### Solve longest common subsequence in a non dynamic programming way? [closed]

I am working on the longest common subsequence (LCS) problem while learning dynamic programming. Below is the Java code I created to solve the problem, which is not dynamic programming as far as I ...
193 views

### How to understand the Bellman Equation in plain English terms?

So on my course we're dealing with a more basic, simple varition of the Bellman Equation. V(S) = max a(R(s,a)+yV(s')) As far as I can tell... V(S) = Value of a state max a = Maximum over all ...
177 views

### Egg dropping puzzle - clarification of problem statement

I was trying to understand the egg dropping puzzle. The problem objective is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst ...
184 views

### What is the complexity of comparing point sequences?

Given two sorted arrays of floating point numbers $X$ and $Y$, we can define the S-distance as follows. The S-distance is defined as the minimum cost associated with the transformation of one point ...
78 views

### Get count of longest zigzag sub-sequences

I know how to get longest zigzag sub-sequence and length of it. There are several methods available for that. But some times there are many sub-sequences available which have same length. How to ...
56 views

266 views

### Variant of the knapsack problem and box stacking

I'm facing a problem described as follows: You are given a set of $n$ types of rectangular 3-D boxes, where the i-th box has height $h_i$, width $w_i$, depth $d_i$ and value $v_i$. You want to create ...
290 views

### A knapsack problem with variable knapsack size

I've come across this problem and I can't find a decent DP solution for it. Given an initial amount of money and a bunch of items to buy (where each item has a 'value' and 'price' assigned to it), ...
38 views

### Online set cover variant? Routing of requests

We have a set of $k$ path requests from $src$ to $dst$ that arrive sequentially. Each request may have multiple paths, but can choose only one of them. For example, in the Figure shown, there are ...
104 views

### Transform 2D range query matrix into segment tree to make memory usage lower

Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-...
36 views

### Algorithm to check if exists a valid streaming sequence in O(n)?

Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 ...
71 views

### Activity planning problem

Given a sequence of N activity durations, the time P of pause between activities, and D, the length of a day (there are no breaks between days, only between activities in a day), what is the minimum ...
435 views

### Number of possible sequence partitioning

Given a sequence of 1 and 0 elements, what is the number of possible partitioning of the sequence in sub-sequences (not necessarily consecutive elements, and any number of sub-sequences are allowed) ...
75 views

### Are there Dynamic programming speedups for $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$

I am wondering if there are dynamic programming speedups for the minimization problem $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$. Now I understand that its highly unlikely that such thing would exist for ...
893 views

### Understanding tables in Dynamic programming

I came across this problem that asks you to implement a regular expression matcher with support for '.' and '*', where '.' Matches any single character. '*' Matches zero or more of the preceding ...
529 views

### Knapsack progblem with two conditions

I want to create an algorighm (with dynamic programing) similar to 1/0 knapsack problem but, I have one extra condition isVegetable or isFruit. Assume we have N food items where we know ...
30 views

### Can dynamic programming have n OPTimal subproblems?

I want to develop an algorithm which finds the optimal sequence of multiplications to multiply n matrices. For example, if we have: M1 x M2 x M3 x M4 x M5 x Mn The algorithm should place the optimal ...
40 views

### The path with the highest sum of weights

Mr. Katsaros owns a rectangular olive grove divided into 5 rows and 4 columns. He notes down the amount of olives (pounds) possibly obtainable from each of 20 square sections. The picking starts from ...
181 views

### Knapsack problem question

Based on this video, the tutor explains the knapsack problem with dynamic programming approach. One thing is not cleared in this video, which is my main question. All the values on the first row (...
254 views

### Levenshtein distance algorithm with bits

I need to write a function that gets an array of bytes at the input and 2 integers (minDist and maxDist). The calculation algorithm understands this field as a bit sequence starting from the LSB (...
354 views

### How does matrix chain multiplication problem has an optimal substructure?

We solve Matrix chain multiplication problem considering the optimal solution to subproblems but what I cant get through my mind is how this problem has an optimal substructure? For eg. consider if ...
377 views

### Longest subsequence accepted by DFA (Dynamic Prog algorithm)

Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists. This problem has a runtime ...
105 views

### Dynamic Programming on bracketed sequences

I am currently working on the following problem that involves developing a dynamic programming algorithm for finding the length of the shortest fully bracketed expression (FBE), $y$ that contains a ...
63 views

### Counting restricted partitions

Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$:  N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq ...
196 views

### Shortest Non-Subsequence String With Constant-Size Alphabet

Let $S[1..n] \in \Sigma^*$ be a string of $n$ symbols over the alphabet $\Sigma$ where $|\Sigma| \in \mathcal{O}(1)$. Determine a shortest string which cannot be obtained from $S$ by deleting some (...
44 views

### Inserting values at maximal distance from current value

I have the following problem. Given an array A, filled with 0s, we should set some elements to be equal 1, considering such rules: If all elements equal 0,set A[0] to 1 Next 1 should be set at ...
479 views

### Control of the combinatorial aspects of a dynamic programming solution

I am exploring how a Dynamic Programming design approach relates to the underlying combinatorial properties of problems. For this, I am looking at the canonical instance of the coin exchange problem: ...