# Questions tagged [dynamic-programming]

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

607 questions
Filter by
Sorted by
Tagged with
514 views

### Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised

Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. ...
465 views

### How to divide a line of numbers into N groups such that the sums of each group are closest to their mean using dynamic programming? [duplicate]

I have M numbers arranged into a line. I need to divide the line into N groups without changing numbers order such that the sums of the numbers of each group are closest to the mean of these sums by ...
121 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 ...
206 views

Different machine has different efficiency on different tasks, like: ...
22 views

I was wondering if anyone could point to some sort of review to this paper "Table Design In Dynamic Programming" by Peter Steffen and Robert Giegerich? https://dl.acm.org/citation.cfm?id=1182768 Has ...
237 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-...
124 views

### How to solve a DP problem that minimizes a sum of cubic powers?

I am trying to practice some coding problems and I came upon this problem: As electricity prices are soaring, there must be a way to reduce wastage by increasing the utilization of heavy duty ...
44 views

### invariant of bin packing

We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We ...
131 views

### Hitting probability of random walk within given number of steps

Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates. What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially? We can ...
68 views

### Word Problem over Finite Groupoids

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://...
101 views

### Join Order Optimization

Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player What is the optimal join order? Based on the schema on the following picture: I am suppoused (and that's what I tried) to use ...
434 views

### Finding the largest possible area covered by M rectangle under a given histogram

Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles ...
198 views

### Edit Distance Algorithm (variant of longest common sub-sequence)

I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming. The problem is defined as ...
88 views

### In which order to solve subproblems when using memoization?

I am currently trying to solve a task with memoization. I have following recursion: A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) ) I am not sure in which order the sub-problems should be ...
576 views

### dynamic pseudo-code for simplified coin changing algorithm

As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible ...
189 views

### Interview Questions for Minimum Cost of Tasks

I got this problem as an interview questions and I was blank all the way, I thought it was pressure but as I try to do it now I am still blank, anyway to solve this problem, I am blank so a solution ...
92 views

### Minimum number of deleting palindromes to delete whole string

Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only ...
95 views

### To check if a chain with $n$ links can be “folded” into a size at most $L$

Given a chain of $n$ links, each of length $a_1, a_2,..a_n$, where each $a_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists ...
39 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 ...
72 views

### Bertrand's ballot theorem

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this If i number of people voted for A and j number of people voted ...
79 views

### All pair shortest path in a tripartite graph

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
149 views

### Carpet into Box

Given a carpet of size a * b [length * breadth] and a box of size c * d, one has to fit the carpet in the box in the minimum number of moves. A move is to fold the carpet in half, either by length or ...
75 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 ...
280 views

### Floyd Warshall's All pair shortest path problem does not evaluate all possible paths

We know that the FW all pair shortest path is a Dynamic Programming (DP) approach to solving the problem. Being a DP, it smartly evaluates all possible options before deciding the final option at each ...
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 ...
245 views

### Merging balls interview problem

Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks. You are given $n$ balls on the table and all the balls are rolling towards the ...
50 views

38 views

### Text Segmentation Problem give Word Frequencies in a Universe

Given a dictionary of words and their frequencies (how many times they appear in a universe and given a string(no spaces, punctuation, etc.). What is the best way to segment into individual words? I ...
36 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 ...
240 views

### Algorithm : Visiting all stations in minimum time with additional constraints

I was given this question and not sure how to solve this. This is a DP minimization problem ? Problem : There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to ...
58 views

### Computing number of ways to make change

Given a list $C=[c_1,c_2,\dots,c_k]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total ...
577 views

71 views

### Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?

I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop. Is this reasoning correct or is there more to it?
34 views

### Count paths in matrix that visit each number exactly once [duplicate]

Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$. We want to count the number of paths that start ...
614 views

### Technique for converting recursive algorithm to DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
84 views

### Prooving by Pigeonhole principle

I've been given a question to solve: ...
446 views

### set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
195 views

### Maximize interleaving subsequences two digit arrays/strings

Suppose I have two digit arrays, A and B as follows A = [3,4,5,6] B = [9,8,3] Now, I have ...
I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$. For ...