# 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
482 views

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 ...
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+...
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 ...
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 ...
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 ...
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. ...
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). ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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/...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...