Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
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 ...
0
votes
0answers
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 (...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
56 views

Minimise given size using dynamic programming

Given numbers $0<x_1<x_2< \dots<x_{n^2}<1,$ for every subset of $n$ of them $x_{i_1}<x_{i_2}< \dots<x_{i_n},$ let us consider the size: $$\max\{x_{i_1}, x_{i_2}-x_{i_1}, x_{i_3}...
0
votes
2answers
393 views

Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers

This question is doable if you can calculate the number by multiplying f(n-1) and f(n-2). Is it possible to do this question if we entirely want to skip ...
0
votes
1answer
360 views

Print (not count) all possible path classic climbing stair problem)

I came across this classic question and found may many solution to it. for loop and DP/ reclusive + memorization. Also found a twisted version of the questions asking to print all possible path ...
3
votes
1answer
570 views

Time Complexity: Intuition for Recursive Algorithm

I decide to learn more about dynamic programming, so I started reading the Dynamic Programming chapter from the CLSR book. The first example problem presented there is Rod Cutting (15.1). Given a rod ...
0
votes
1answer
61 views

Build all valid parenthesis in polynomial time

Given some binary operator $\otimes : X\times X\to X,$ and list $x_1,\dots,x_n$ where $x_i\in X,$ can all possible expressions in $\otimes$ be computed within a number of operator applications ...
0
votes
1answer
669 views

Prove Recursive formula (Dynamic programming) N(C,i)

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
0
votes
0answers
39 views

Q-Learning Error Bounds

I have searched a lot for this, but apparently there is no result on calculating any bound on the error $||Q-Q^*||$ when I stop Q-learning after say $N$ iterations ($Q$ is the vector of Q-values at ...
2
votes
0answers
1k views

k-way set partition problem--dynamic programming solution

I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem Among other things, they present a DP approach to solving the equal subset ...
0
votes
3answers
82 views

Fibonacci Series with Dynamic Programming

We can compute Fibonacci numbers by means of dynamic programming approach. If we do not store intermediate solutions, we cannot use them for future necessities. In this case, asymptotic complexity ...
1
vote
0answers
1k views

Longest increasing subsequence (Dynamic Programming)

I have written the following recursive structure for finding length of longest increasing subsequence. ...
1
vote
1answer
22 views

A “packing” optimisation problem with application in dynamic programming

I'm interested in the following problem : Input : an integer $n$, and $k$ increasing functions $f_i:\mathbb{N}\rightarrow\mathbb{R}$, such that $f_i(0)=0$ for all $1\le i \le k$ Output : $k$ ...
2
votes
1answer
406 views

Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms

From my understanding, a problem amenable to a dynamic programming solution has these two properties: Overlapping Subproblems — The same subcase (a subsection of the overall problem) keeps ...
1
vote
0answers
84 views

Comparison of time-dependent traveling salesman heuristics

I'm looking into implementing a heuristic for the time-dependent traveling traveling salesman problem (TDTSP) that completes in a certain amount of time. There are a wide range of possible ways to ...
3
votes
1answer
357 views

Finding the length of the longest increasing path in a matrix

Problem: Given a matrix, find the length of the longest increasing path. We can move up, down, left, or right. Example: $$ \begin{pmatrix} 1&2&3&4\\2&2&3&4\\3&2&3&...
1
vote
1answer
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 ...
1
vote
0answers
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), ...
2
votes
1answer
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 ...
0
votes
1answer
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-...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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) ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 (...
0
votes
0answers
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 (...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 (...
2
votes
1answer
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 ...
1
vote
1answer
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: ...
2
votes
1answer
462 views

Find all the cumulative sums in a DAG

Let's call G a DAG (directed acyclic graph) with N nodes labeled with a natural value. We define the cumulative sum of a node v as the sum of the value of all the ancestor nodes of v (including v). ...
0
votes
1answer
61 views

Dynamic graph (?) - combination of connections between vertices that for each 3 exist min 1 edge

I have to find number of ways (combination) to create graph that for each 3 vertices there are minimum 2 vertices connected. There is n vertices. For example when n=3, there are 7 possible ...

1 3 4 5 6 7 13