Questions tagged [dynamic-programming]

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

163 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
31 views

Dynamic programming algorithm to merge two lists maintaining relative order and minimizing cost between elements

So I have a problem in which I have two lists of physical exercises (routines) and I want to merge them such that the merged list maintains the relative order of the previous lists, so for example, if ...
0
votes
0answers
28 views

Multiple Optimal Solutions in Dynamic Programming

In 2-D dynamic programming problems like Edit Distance and binary knapsack, there can be multiple optimal solutions. By tracing back from the last element in the matrix one could trace out all the ...
0
votes
0answers
30 views

Matrix chain multiplication using dynamic programming

Consider we need to solve the Matrix chain multiplication using dynamic programming for this problem : The table for min. cost is shown below : Edit : Reference https://www.radford.edu/~nokie/...
0
votes
0answers
36 views

Catching ball - finding the maximum number of caught balls

I'm attempting to solve the following problem: Balls are falling from the sky. We know at which location (on a straight line) will each ball drop, and we know the time (in seconds) at which ...
0
votes
1answer
90 views

Dynamic programming

Got a question and can't manage to find an answer, so help will be appreciated. I should design an algorithm, using dinamic programming, that gets as an input a matrix, named A, with n rows and k ...
0
votes
0answers
116 views

What are some variants of the rod cutting problem?

I am looking at the possible implementations for solving the rod cutting problem (CLRS). Do you know of any variants of this problem and their use in industry?
0
votes
0answers
51 views

A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
0
votes
0answers
30 views

Schedule a Seminar in Minimum Time

There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
0
votes
0answers
95 views

Minimizing the distance from a set of nodes in a tree

We have a binary tree with n nodes and a number k which signifies the number of nodes that we put on a set. What is the optimal algorithm to select a set consisting of k nodes, that minimizes the ...
0
votes
0answers
25 views

Dynamic programming algorithm with an O(n) performance that will give the optimal solution

I am currently learning the dynamic substructure and optimal solution for the coin change-making, and one of the questions given from my teacher is to describe an overall O(n) dynamic programming ...
0
votes
0answers
25 views

Dynamic programming solution to Matrix chain multplication order - time complexity

I am unable to understand why the dynamic programming solution to Matrix chain multiplication order problem is O(n^3). Can someone please help understand the reasoning? To me, it looks like the ...
0
votes
0answers
67 views

How to solve this dynamic programming puzzle on matrix?

We are given 4 integers N,M ,Q and Z. Initially,the matrix has all zeroes in it. We have to perform Q operations on the matrix. In each operation, any cell of the matrix can be selected(same cell ...
0
votes
0answers
44 views

Can anyone provide proof of second equation of rod cutting problem in CLRS section 15.1

While going through ROD CUTTING problem of DP from CLRS, I noticed the optimal structure of the rod cutting problem is : ๐‘Ÿ๐‘—=max{๐‘๐‘›,๐‘Ÿ1+๐‘Ÿ๐‘˜โˆ’1,๐‘Ÿ2+๐‘Ÿ๐‘—โˆ’2,...,๐‘Ÿ๐‘—โˆ’1+๐‘Ÿ1} In overhead approach, ...
0
votes
0answers
49 views

Counting number of apples in an apple tree with given number of layers

This problem comes from a competitive programming question, and it seems to require dynamic programming. There are several layers of apples arranged in a formation with each apple having a value ...
0
votes
0answers
52 views

Job scheduling with minimum makespan

You are given n jobs, m workstations and an n ร— m two-dimensional task matrix T of the time each job will spend at each workstation. Each job becomes available at a specified time and may be processed ...
0
votes
2answers
149 views

Given matrix, count paths visiting each number exactly once

We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in ...
0
votes
0answers
297 views

Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming

I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below: Regular chores with a start time and end time (a real-...
0
votes
0answers
40 views

Two-dimensional Range Minimum Query under a constraint

So, I have trouble understanding and solving the following question: You are given a 2D array. Design an algorithm that, given two coordinates (each with two indexes ofc), returns the minimum in the ...
0
votes
0answers
99 views

Dynamic Programming solution for finding shortest distance to travel between points

So consider a person located at point $c$ (let's say $c=140$). Given a set of other points, for example, $P = \{100, 50, 190\}$. The cost of traveling to a point $P_i$ is then $|c-P_i|$. Points can be ...
0
votes
0answers
34 views

Is there any optimization technique for DP with $f[i][j] = \min_{z<j}{f[i-1][z] + G[i][j-z]}$ where G[i] is increasing and positive?

Given a dynamic programming formula like $f[i][j] = \min_{z<j}{f[i-1][z] + G[i][j-z]}$ where $G[i][j]$ is positive and increasing along $j$ for all $i$s. Is there any optimization to make it ...
0
votes
0answers
39 views

findining the smallest sum of squared lengths of the intervals I_{k}

Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to ๏ฌnd k intervals $I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one of ...
0
votes
0answers
101 views

Multi Knapsack each with different constraints

It seems that there's no end to knapsack variationsโ€ฆ here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
0
votes
0answers
188 views

Intuition behind Floyd-Warshall being faster

I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm: Let $dp[i][j][n]$ denote the shortest path from $...
0
votes
0answers
49 views

What will be an O(n) solution for this?

Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at ...
0
votes
0answers
62 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 (...
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 ...
0
votes
0answers
210 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
846 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
41 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 ...
0
votes
0answers
38 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
76 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 ...
0
votes
0answers
38 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
0answers
299 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 (...
0
votes
0answers
167 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-...
0
votes
0answers
85 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 ...
0
votes
0answers
87 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 ...
0
votes
0answers
79 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 ...
0
votes
0answers
367 views

Understanding Dynamic Programming through this example

I have trouble understanding The classic Mailbox Manufacturers Problem. You can read it here: https://open.kattis.com/problems/mailbox I have also found a solution text: http://www.ida.liu.se/projects/...
0
votes
0answers
193 views

Question regarding the Dynamic Programming solution for Rod Cutting Problem?

As per the book "Introduction to Algorithms" , to solve the rod cutting problem for a given length n, we basically iterate over all possible lengths of the first part , and calculate the optimal ...
0
votes
0answers
1k views

What algorithm does OLA and UBER use for allotting taxis

More specifically : lets say i have 5 taxis , each available for booking at t=0; i have two days (48 hrs) with me how can I maximise their booking . I may not be able to clarify the question , this ...
0
votes
0answers
51 views

Tracking Solution with Multiple Matrices in Dynamic Programming

We recently figured out a Dynamic Programming solution to compare two trees using concepts of edit distance in strings. It goes something like this- $A[i', i, j', j] = \min \begin{cases} B[i', i-1, ...
0
votes
0answers
151 views

what is approach of solving MINUS on SPOJ?

Link: http://www.spoj.com/problems/MINUS/ I have an Idea, after doing n-1 operations one can see that there is just + and - coefficients before each number that matters. For eg. given sequence: 12 ...
0
votes
0answers
159 views

Finding the shortest tour of a Pyramidal traveling salesman problem

We have a directed graph $G=(V,A)$ with $V=\{1,2,...,n\}$ where for each $(i,j)$ the distance $l(i,j)\in A$ is known. We want to find a pyramidal tour that has minimal length and that includes all ...
0
votes
0answers
85 views

no of ways to fill a row (1xN grid) with a set of 1D bars with some constraints?

Given a row of length N, and a set of 1D bars having lengths A[1...M], how many ways I can fill the row? A is an integer array, the bars are having dimensions $\{1\times A_1,1\times A_1,1\times A_1,....
0
votes
0answers
275 views

Dynamic programming problem โ€” Finding a suitable algorithm

Bob has $2$ cranes and $M$ available containers ($1 \leq C_i \leq M$) and he has to do $N$ transports from one container to another given an input list (the order of the transports must be respected). ...
0
votes
0answers
84 views

Figure out recursive function for this problem

I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function. There is N students (N is even) in class. ...
0
votes
0answers
41 views

Find cheapest path from 1st city to the $n$th city

The title may be a bit misleading, but this is essentially a DP problem. The problem is that we have $n$ cities labeled from $1, ... n$ and we are trying to find the cheapest way to travel from 1 to $...
0
votes
0answers
323 views

Proving a dynamic programming recurrence for coin exchange correct

Suppose I have $n$ kinds of coins $c_1, c_2, \dots, c_n$. I'm given: $S$, an amount of money I should construct with minimum number of coins. I came into the following formula: $$ T(n,S) = \begin{...
0
votes
0answers
233 views

Weighted Interval Scheduling with constraint

How do we solve the weighted interval scheduling problem if given a maximum weight? I understand the solution for the problem when we are simply interested in the maximum weight possible, but how do ...