Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
607
questions
3
votes
1answer
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. ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
2
votes
1answer
206 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
0
votes
0answers
22 views
Analysis Or Review Of Article “Table Design In Dynamic Programming”
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 ...
0
votes
0answers
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-...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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://...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
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 ...
3
votes
2answers
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 ...
1
vote
1answer
50 views
Trying to understand the question(well spaced points ?) better
Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j}...
2
votes
1answer
310 views
Lexicographically smallest down-right path in matrix
Here is the problem which I thought was simple dynamic programming, which is however not the case.
Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
1
vote
1answer
250 views
Shortest path from source to all vertices, but with some wildcards
Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).
You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
1
vote
2answers
123 views
Doubt over the index value used in dynamic programming
I was going through Count All Palindromic Subsequence in a given String where I've to count all the palindromic subsequence of a given string.
After seeing the brute force(recursive solution), I went ...
2
votes
2answers
110 views
Recursion to DP Solution
There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
1
vote
1answer
288 views
Maximum product of contiguous subsequence over $\mathbb{R}$
For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here).
Let us first show how to solve the ...
0
votes
1answer
120 views
Dynamic Programming Problem on Tree
Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had ...
1
vote
1answer
71 views
How does dynamic programming work in this example(generating the tables )
For example, a sequence has the defined growth property: if it is a
sequence of positive integers $a_{1}, a_{2}, a_{3}....a_{n}$ and such
that:
$a_{1}=1.$
$a_{n+1} \leq$ Max$_{1\leq i \...
1
vote
0answers
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 ...
0
votes
0answers
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 find k intervals
$I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one ...
-1
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
577 views
Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time
Let PARTITION-INTO-THREE-SETS be defined as following:
Input: Positive integers $a_1, ..., a_n$
Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup ...
1
vote
1answer
82 views
Finding optimal multiplication order and optimal binary tree
I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.
Consider the following ...
1
vote
1answer
573 views
What Are the Ideas Behind Variations of the Coin Change Problem?
Problem: given a set of n coins of unique face values, and a value
change, find number of ways of making change for ...
1
vote
0answers
132 views
Is MCTS an appropriate method for this problem size (large action/state space)?
I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t)...
1
vote
1answer
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?
1
vote
0answers
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 ...
2
votes
2answers
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 <...
2
votes
4answers
84 views
1
vote
2answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
46 views
Max sum cyclic path of fixed length in matrix
Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
1
vote
1answer
73 views
Number of contiguous subsequences summing to a given target
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 ...
