Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
551
questions
2
votes
0answers
12 views
Seeking an algorithm for finding the partition of data on an interval that maximizes the minimum fitness among the blocks
In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness ...
0
votes
0answers
50 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 ...
0
votes
2answers
77 views
number of permutation with k inversions
We are given two numbers N and K.
N <= 10^9.
K<=min{1000,(N*(N-1))/2}
We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.
If N was <= 10^3. It would ...
3
votes
4answers
84 views
Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people
Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.
The total value of $n$ gifts ...
-4
votes
0answers
64 views
1
vote
1answer
48 views
Dynamic programming and multiple optimal solutions
I have tried researching how I can handle multiple optimal solutions based using dynamic programming. The answer is found from this question is simply that you have to backtrack. What if this is not ...
2
votes
1answer
65 views
Algorithm to find longest path in a tree that is smaller than x
Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any ...
3
votes
1answer
42 views
DP for Weighted Interval Scheduling: why is sorting by finish time necessary?
Problem In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has ...
3
votes
2answers
47 views
Compute highest-scoring segmentation
I have the following problem:
There is a "clean" sequence of sequences, say:
clean = [
[1, 2],
[3],
[4, 5]
]
And a "noisy" sequence which is not ...
2
votes
0answers
33 views
Dynamic Program for this Weighted Possion-Binomial Problem?
Setup: Suppose we have $n$ independent Bernoulli random variables, say $\boldsymbol{X} = \{X_1, ..., X_n\}$ each with prior $\mathbb{P}(X_j = 1) = p_j$, and weights between $-1$ and $1$, say $W = \{...
1
vote
1answer
33 views
Ford Fulkerson maximum flow for all vertices
Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, ...
0
votes
0answers
22 views
Can anyone provide proof of second equation of rod cutting problem in CLRS section 15.1
While going through ROD CUTTING problem of DP from CLRS, I noticed the optimal structure of the rod cutting problem is :
𝑟𝑗=max{𝑝𝑛,𝑟1+𝑟𝑘−1,𝑟2+𝑟𝑗−2,...,𝑟𝑗−1+𝑟1}
In overhead approach, ...
0
votes
0answers
45 views
Counting number of apples in an apple tree with given number of layers
This problem comes from a competitive programming question, and it seems to require dynamic programming.
There are several layers of apples arranged in a formation with each apple having a value ...
2
votes
1answer
65 views
Gas Station problem : Fixed path variation
Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path ...
2
votes
0answers
22 views
Selecting objects to maximize value while under multiple constraints
I think it will be best to explain the problem first and then explain what I am thinking:
I have a dataset similar to the following:
...
1
vote
0answers
40 views
How to approach backtracking when using immutable types (Python)? [closed]
In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to ...
2
votes
2answers
72 views
How can I solve this problem using dynamic programming?
I'm stuck in this problem and I would need some help:
Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. ...
2
votes
2answers
94 views
How can we find a palindrome within a string?
The problem requires us to find the substring within a string which happens to be a palindrome. Multiple palindromes are also allowed.
For example, in "LODHIHDAK" "DHIHD" is a palindrome.
Comparing ...
1
vote
1answer
41 views
Winning strategy using Dynamic Programing
Let $G=(V,E)$ be a DAG and let $v_0\in V$.
Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v_i,x)$, ...
0
votes
1answer
56 views
Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum
count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.
This is my recursive algorithm, what is wrong here?:
...
1
vote
1answer
79 views
Given price and number of pages of each book, What is the maximum number of pages you can buy?
You are in a book shop which sells n different books. You know the price and number of pages of each book.
You have decided that the total price of your purchases will be at most x. What is the ...
1
vote
1answer
91 views
How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)
Can someone tell me what am I doing wrong?
Problem: https://codeforces.com/contest/22/problem/B
Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) )
Eg:
...
2
votes
3answers
179 views
Selecting items from two arrays without duplicate indices to get maximum sum
Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you ...
1
vote
0answers
25 views
Determining the DP subproblem given a problem
I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems.
For example, consider 2 similar problems.
Given a set of 1, 2, and 3 steps you can take, ...
0
votes
0answers
28 views
count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]
Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths
of a given length n from a given start node, so that fjor every path applies:
a) no vertex ...
0
votes
1answer
41 views
How to solve this job scheduling programming problem?
I am trying to solve this question. The question is a variation of job scheduling. There are n processes given to you with their execution time Ti and individual ...
2
votes
2answers
474 views
Split array into contiguous subarrays of approximately same sums
My question is similar to this splitting question, but my objective function is different.
Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty ...
0
votes
0answers
23 views
What does 'recursion with no explicit stages' mean in relation to dynamic programming?
I have the following excerpt from one of my assignments, essentially asking me to build on a previous formulation. However, while I can think of improvements, I have no idea if they fit the 'no ...
1
vote
1answer
32 views
Shrinking Item 0-1 Knapsack problem
I have encountered a variant of the knapsack problem with shrinking items.
Effectively, it is a 0-1 knapsack problem where the initial weight of each item is $W(n)+V(n)$ and their value is $V(N)$, ...
3
votes
2answers
59 views
Maximize number of museums visited in a day
Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day.
Suppose that no time is needed in ...
0
votes
0answers
38 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 ...
1
vote
1answer
80 views
Number of ways of tiling a 3*N board with 2*1 dominoes problem
I came across this problem,
Tiling with Dominoes
and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a ...
3
votes
1answer
77 views
Reductions between LIS and LCS
Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
4
votes
1answer
67 views
Calculating all products of $n-1$ factors when given $n$ factors
Let's assume we have an operator
$$ \times: E^2\to E$$
of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$.
We're ...
2
votes
3answers
164 views
Do all recursive problems have optimal substructure?
I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved ...
4
votes
4answers
268 views
Algorithms for 2-colouring a 2 x N matrix
Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions.
An example of all possible ...
0
votes
0answers
15 views
Why does the knapsack dynamic programming solution has runtime of O(nW)? [duplicate]
Can you please help me analyse the runtime of the knapsack dynamic programming (which i have seen somewhere is O(nW))?
This is the algorithm i an using:
Define M[i,s] to be the maximum value that ...
0
votes
1answer
47 views
Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm
I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1} = app \quad \& \quad r(j) \leq p $ and (...
1
vote
1answer
120 views
Dynamic programming - maximize sum of functions subject to constraints
Let $\{f_i\}_{i=1}^{k}:[0,k]\to\mathbb{Z}$.
The problem: Maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le k$
I think we suppose to come up with a ...
4
votes
0answers
68 views
Maximum weight independent set in a King's graph
I would like to find a maximum weight independent set in a finite section of a King's graph.
For an $m\times n$ King's graph where $n \ll m$, we can use an $O(2^{2n} m)$ bitmask dynamic programming ...
1
vote
1answer
304 views
How many ways to express N as sum of 2, 3 and 5?
I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7:
N = 5 + 2
N = 2 + 5
N = 2 + 2 + 3
N = 2 + 3 + 2
N = 3 + 2 + 2
But most of I found on the Internet that the ...
2
votes
1answer
70 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 ...
1
vote
1answer
51 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
416 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
309 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 ...
1
vote
2answers
90 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
131 views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
0
votes
0answers
20 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
112 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
122 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 ...
