Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
539
questions
2
votes
0answers
18 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:
...
0
votes
0answers
21 views
PAN card verification problem [closed]
Given a paragraph P of words which contain some PAN card Numbers. Count the number of distinct valid PAN card numbers in P.
A valid PAN card number is a 10 length alphanumeric word of the form: "...
0
votes
0answers
23 views
Longest common substring [on hold]
What does each cell of dp table in case of" longest common substring" denote?
I am a bit confused. consider the strings X ="geek" and Y ="ge"
When we construct the dp table for this ( string X is ...
1
vote
0answers
15 views
How to approach backtracking when using immutable types (Python)? [on hold]
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 ...
1
vote
0answers
33 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
85 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
38 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
35 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
72 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
47 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
73 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
22 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
27 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
116 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
22 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
29 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
48 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
36 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
28 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
60 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
64 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 ...
1
vote
3answers
90 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
264 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
45 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
66 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
66 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
98 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
68 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
50 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
357 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
200 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
67 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
83 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
69 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
113 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
39 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
47 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
59 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
100 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
266 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
56 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
65 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
184 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
132 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
57 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
85 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
25 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 ...
