# Questions tagged [dynamic-programming]

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

192 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0answers
482 views

1answer
20 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 ...
0answers
62 views

### Dynamic programming algorithm to find largest triangle in binary square matrix where elements equal “1”

I'm struck how to find DP recurrence for: You are given a binary square matrix M of size nxn. We define a (p,q, l)-triangle of M, where p >= 1, q >= 1, L >= 1, p+L >= n+1, and q+L >= n+...
0answers
37 views

### 0/1 Knapsack problem. How does the total weight does not exceed the limit?

I am trying to wrap my head around the knapsack problem algorithm. I understood the most of it except one tiny thing. On the left is the [val,weight] and on the ...
2answers
138 views

### Count the possible plans for nurses

I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below: The director of a hospital want to schedule a working plan for a nurse in a given period of N ...
0answers
16 views

### Write recurrence for cost minimization

So I am trying to find the recurrence for this problem but I feel like it is missing something. An ice cream shop is looking to minimize their operation costs, under the given constraints: They are ...
2answers
43 views

### Two-Sum - Range Allowance Algorithm Design

🧩 What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity? Optimize for runtime over memory complexity. ...
0answers
16 views

### Probability that BST has exact height

Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$. (We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number). ...
0answers
27 views

### Number of complete traversals of the circle in generalised Josephus problem?

In the generalised Josephus problem, n people stand in a circle and every kth person is eliminated until only one person is left. The last person left standing can be found using dynamic programming (...
1answer
56 views

### How is equation 1 simplified to equation 2 as shown below

In CLRS (Intro to algorithms) on page 362, it says eqn(1) : can be simplified to this equation(2): I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal ...
0answers
34 views

### Optimal partitioning of n-arrays

You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays. The goal is to partition those arrays into K ...
0answers
76 views

### Why the time complexity for following pseudocode is O(n^2)?

So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS. Here's the rod-cutting problem statement: Given a rod of length n inches ...
1answer
41 views

### Interval Scheduling problem with more than 1 machine

There are 2 machines. Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine The list of n ...
1answer
54 views

### Dynamic Programming - Tiling Question

I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which ...
0answers
67 views

### Get the maximum sum of n items below a threshold

Consider a modified Knapsack Problem where: The number of items to be included is fixed. The value of each item is equal to its weight. Therefore, given a set of numbers, a threshold and the number ...
0answers
40 views

### Linear Partition problem (Dynamic Programming) in a circular array

I am practicing algorithms for the last couple of days and I came across this question, the gist of which is: Given apples and oranges arranged in a circle indexed form 1 to n , where n is an odd ...
0answers
31 views

### Alternate Knapsack Implementation

I came across a question that requires an alternate implementation converse to the normal Knapsack which is based on a 0-1 logic of considering whether or not to consider an item for the optimal ...
0answers
98 views

### How to trace Subset from Boolean DP table in the Subset Sum Problem

I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result. My questions are. How did someone conclude that ...
0answers
55 views

### Variant of box stacking algoritm

I'm trying to solve this problem which I believe is a variant of box stacking algorithm. Problem : Suppose I have n boxes each with height h, width w, length l. Now if one box can fit inside another ...
0answers
84 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 ...
0answers
51 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 ...
0answers
44 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/...
0answers
42 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 ...
1answer
115 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 ...
0answers
306 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?
0answers
35 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 ...
0answers
137 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 ...
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 ...
0answers
85 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 ...
0answers
56 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 ...
2answers
177 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 ...
0answers
343 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-...
0answers
46 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 ...
0answers
148 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 ...
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 ...
0answers
43 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 ...
0answers
133 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 ...