Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
560
questions
1
vote
1answer
30 views
Multiple choice knapsack dynamic problem
Giving a the following:
A list of a store items $T=\{t_1, t_2,...,t_n\}$.
A list of prices of each item $P=\{p_1, p_2,...,p_n\}$.
A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$...
1
vote
1answer
35 views
Converting a greedy algorithm to a dynamic programming algorithm
Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:
First, find a maximum indpendent set of ...
0
votes
1answer
45 views
How to compute total number of subsequences of length k from a word of length N?
A subsequence of a word is obtained by dropping some letters from it. The letters
that are dropped need not be consecutive. For instance, ba, bna and banaa are all
subsequences of the word banana.
We ...
0
votes
0answers
20 views
Dynamic programming solution to Matrix chain multplication order - time complexity
I am unable to understand why the dynamic programming solution to Matrix chain multiplication order problem is O(n^3). Can someone please help understand the reasoning?
To me, it looks like the ...
2
votes
1answer
20 views
Minimum words in a string given a dictionary
The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
1
vote
1answer
19 views
Grokking pseudo-code for solution to gas station problem
I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
3
votes
0answers
37 views
Forbidden Sequence Dynamic Programming
Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the ...
1
vote
0answers
33 views
How does the asterisk (*) work in the wildcard matching problem?
This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-...
1
vote
2answers
39 views
Find the minimal tank capacity to be able to travel from any city to any other
There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} > 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find ...
2
votes
0answers
19 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
54 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
87 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
87 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
65 views
1
vote
1answer
51 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
70 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
45 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
34 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
46 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
67 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
23 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
46 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
95 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
60 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
80 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
98 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
202 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
626 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
61 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
39 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
83 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
125 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
177 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
136 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
345 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 ...
