We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
28 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
170 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
236 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 (...
2
votes
1answer
331 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
359 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
98 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
52 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
167 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
410 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
407 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 ...
0
votes
1answer
111 views

Bottom-up algorithm to build subset of maximum weight

I have this problem of obtaining a subset of maximum weight from a given array of size n (the i-th element is the weigth of the item i) - lets call it P. The only restriction is defined by an array R ...
1
vote
0answers
350 views

How to “convert” a top-down solution to a bottom-up algorithm? [duplicate]

When I'm working on a algorithm problem, I can usually find a top-down solution that works with recursion. Then for optimization purpose I try to do a bottom-up approach (dynamic programming) to ...
1
vote
1answer
675 views

Printing actual solutions for the coin exchange problem

As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight ...
2
votes
1answer
713 views

Dynamic Programming for a variant of the coin exchange problem

I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem: Given a value N, if we want to make change for N cents, and we have ...
2
votes
1answer
127 views

Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?

The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So ...
1
vote
0answers
37 views

Find minimum amount of feature combinations reproducing certain coloring of objects

PROBLEM Given a set of features $A = \{a_1, a_2, \ldots, a_m\}$. You have a set of objects $X = \{x_1, x_2, \ldots, x_n\}$ such that each object has certain combination of features. Some objects can ...
3
votes
2answers
835 views

Find longest subsequence in array with given condition

I am given an array $A$ having $n$ elements and an integer $k$. I need to find the longest subsequence which always includes the first element and the subsequence follows the given condition: for ...
1
vote
1answer
700 views

Transforming a bounded knapsack to 0/1 knapsack

Could I transform a bounded-knapsack problem into a 0/1 knapsack problem using the following way-: Example: Lets says I have 3 types of items $n=3$ $p_j=\{10,15,11\}$ $w_j=\{1,3,5\}$ $b_j=\{6,4,2\...
1
vote
2answers
262 views

INOI 2017 Problem 2 - Training

INOI 2017, Problem 2, Training Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order. ...
2
votes
1answer
548 views

DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile. ...
1
vote
0answers
432 views

Algorithm to split an array into minimal number of subarrays where sum of their elements is less than or equal a given one

Title of the question pretty much summarises the question. Here is a concrete example of what I'm trying to achieve with no success. Let's say we have a sorted list (but sorted is not a requirement) <...
2
votes
1answer
146 views

Can there exist more than one optimal solution in a dynamic programming problem?

In any dynamic programming problem can there exist more than one optimal state ? If so how would I enumerate all of them ? For example: in the subset sum problem for the given set $\{-3, -2, 7, 5\}$ ...
0
votes
0answers
122 views

IPL2025 Algorithm problem ? largest sum of n positive number without choosing 3 consecutive number

This question is already asked: To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements https://stackoverflow.com/questions/29249104/maximum-sum-in-...
1
vote
0answers
48 views

Given a Tree decomposition, How to find the tree decomposition of its subgraph?

You are given a tree decomposition of a large graph with not so small bounded tree-width. Suppose now you need to solve a dynamic programming problem inside a subgraph and does not have time to do ...
0
votes
1answer
186 views

Knapsack problem 0/1 with even number of items

So I need to solve the knapsack problem, but I need to make sure that the end solution consists of an even number of items. I found this on an already existing question: You can keep two tables with ...
1
vote
3answers
738 views

Stable matching problem is greedy or Dynamic?

Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.
1
vote
1answer
62 views

Dynamic Programming Recursive Algorithm - Number of heads in a series

So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic ...
0
votes
2answers
2k views

Checkers algorithm - find the best last move in the game given the positions of all pieces

This is the FinalTurn task of the Manganum 2017 challenge. This is the problem and I need to solve it in a timely and performance-efficient manner, which I have not been able to do so far: A ...
2
votes
1answer
249 views

Dynamic programming tree algorithm

We have a network of sensors organized in tree form, where the sensors occupy the nodes. Most of the time the sensors are turned off, until the root sensor wakes up the rest of the sensors. This ...
3
votes
1answer
668 views

Approximate value iteration for continuous state space MDPs

I have a continuous state space MDP as a generative model. I input the state and action and it outputs the reward and the next state. Assume that I sampled $n$ state-reward-states. I wonder how I can ...
0
votes
0answers
77 views

Dynamic Programming: Sum from two subset sums subtracted from each other

There are n values given. Is there a possibility to have two Arrays A and B each containing elements from the given values such that the sum of all elements of A ...
3
votes
1answer
49 views

Maximize the number of satisfied disjunctions

I have ~4000 variables that are used in ~5000 logical formulas, where each formula consists only of conjunctions of the (non-negated) variables. I want to find the maximum number of satisfied formulas,...
0
votes
0answers
81 views

What are the over-lapping sub-problems in the “Turkish Roulette” dynamic Programming challenge?

I came about this problem looking for interesting DP problems. I tried with no luck to find which could be the overlapping sub-problems to explore and solve and tabulate. But it is my belief there ...
1
vote
0answers
456 views

Solving a Rod Cutting Problem

I'm trying to come up with an algorithm for optimizing cutting a rod. Most of the examples I see online are for a stock of rod of a single length and optimizing the way to cut it up for max price. I ...
0
votes
1answer
149 views

When solving dynamic programming in a grid, how do you recognize whether the solution should start at the bottom-right of the table or top-left? [closed]

Example of start top-left, Coin Collecting problem in grid: https://www.youtube.com/watch?v=94FEC_uNwVM Example of start bottom-right, Dungeon Game problem in grid: https://leetcode.com/problems/...
-1
votes
1answer
209 views

Find biggest K, such that any subset of size less than K is not affecting the array

Let's say we have given array $A = \{a_1, a_2, a_3,\dots,a_n\}$ of size $n$, and integer $L$, we want to find biggest integer $K$, such that the array without any subset of size $x, x\leq K$ will have ...
1
vote
0answers
260 views

A variant of the house robber problem

I came across a modification of the classic house robber problem where the robber cannot rob from $l(i)$ houses on the left of $i$th house and $r(i)$ houses on the right of $i$th house. The modified ...
4
votes
1answer
277 views

Why does Banded Needleman-Wunsch give alignments with no more than d base pairs of indels?

A common modification to the Needleman-Wunsch to reduce running time is to only fill in the cells along a diagonal band of the matrix (slides 27/28). Let 2d + 1 represent the width of the band. Then ...
0
votes
0answers
77 views

Does dynamic programming always add one item per sub-solution?

In the 0-1 knapsack problem, I am given a set of items with their weights and the weight that a knapsack can carry. The objective is to maximize the number of items I can carry subject to the fact ...
2
votes
1answer
637 views

Knapsack with an even number of items.

I was asked in an interview to create a knapsack of only even items in n*C time, c being the capacity, n being the number of items to choose from. I tried approaching it with a third dimension, where ...
0
votes
2answers
2k views

Dynamic Programming formulation for hotel problem

There are n hotels given at a0, a1, ..., an such that 0 < a0 < a1 < ... < an. The only places you are allowed to stop are at these hotels, but you can ...
2
votes
3answers
290 views

Modification of dynamic programming for a knapsack problem

We have the following recursive function for the dynamic programming problem for a knapsack problem: \begin{align} V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \...
1
vote
0answers
47 views

Optimal Strategy for Number Reducing Game

There are $n \in \mathbb{N}$ towers, each with a height and a value. Let the positive integers $h_1, h_2, \dots, h_n$ be the heights and $v_1, v_2, \dots, v_n$ be the values, respectively. Two players ...
1
vote
1answer
51 views

Best way for two players to visit a set of graph vertices in a given order

I am struggling with the following dynamic programming problem: Given a complete $N$ vertex digraph and a list of vertices $List$, find a way for two players who start at vertices 1 and 2 ...
0
votes
1answer
134 views

How to calculate the maximum sum over all arrays?

Following question was asked in a online hackathon that has been concluded. Given arrays $A_1,\ldots,A_n$ of length $\ell_1,\ldots,\ell_n$, we want to find cyclically rotate each array in a way which ...
0
votes
3answers
96 views

What is the only condition that would cause the Insert operation of a dynamic data structure to return a “data structure full” error?

I want to know where can I find some resources on this question, because, after researching for a day and half, I couldn't find information specific to my question. Can anyone help me answer my ...
0
votes
1answer
89 views

String edit distance between strings x, y, with restrictions on 'intermediary' strings

This is a problem I encountered in a recent interview test. I achieved a slow-ish solution to it, and I'm keen to figure out the most efficient. Problem Given a starting string $x$, a target string ...