Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
1
vote
1answer
52 views
Given an array of size n, create a sub array with given conditions using dynamic programming
We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level:
1. skip the number in original ...
0
votes
1answer
35 views
How to count the combinations not greater than a given volume in a knapsack problem?
You are given a certain set of items with weight wi and the volume of the bag.
Case:
...
3
votes
1answer
114 views
Use dynamic programming toe
Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. ...
0
votes
1answer
48 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
1answer
24 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 ...
-1
votes
0answers
35 views
divide a gold bar into minimum number of pieces so that it can be divided equally among 7,8 or 9 people
One night nine gangsters stole a gold bar. When the time came for dividing the bar, they faced a problem: two of the criminals put guns to each other's faces. Now it's up to fate whether one of them ...
2
votes
1answer
40 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
0
votes
0answers
19 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
24 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
104 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
37 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
34 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
56 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
98 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
168 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
40 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
44 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
71 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
85 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
42 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
83 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
22 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
37 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
40 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
40 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
41 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
83 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
19 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
93 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
46 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
76 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
60 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
87 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
44 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
81 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
52 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
66 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
35 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
33 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
139 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 ...
1
vote
1answer
37 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
251 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
55 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 ...
0
votes
0answers
20 views
Value iteration in MDP - updating each state once per inner loop?
In value iteration algorithm we update the utility of all possible states ("for each state update its new utility").
After we've updated all states we check to see if the delta is smaller than some ...
1
vote
1answer
51 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
74 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
60 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
32 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
108 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
69 views
