Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
729
questions
0
votes
0answers
44 views
Variant of box stacking algoritm
I'm trying to solve this problem which I believe is a variant of box stacking algorithm.
Problem : Suppose I have n boxes each with height h, width w, length l. Now if one box can fit inside another ...
0
votes
1answer
40 views
Why is a Knapsack problem not an LP problem?
We know that LP can solve optimization problems that have linear constraints and linear objective functions.
A knapsack problem can be formulated into a linear objective function (because it is just ...
0
votes
0answers
71 views
Dynamic programming algorithm to merge two lists maintaining relative order and minimizing cost between elements
So I have a problem in which I have two lists of physical exercises (routines) and I want to merge them such that the merged list maintains the relative order of the previous lists, so for example, if ...
1
vote
1answer
51 views
Using Subset Sum algorithm $O(n)$ times to find the subset
Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
0
votes
3answers
119 views
Minimum number of ways to write a string
Consider the following question
There are K magical pens (numbered 1 through K). You are given strings P1,P2,…,PK (each of which consists of characters from 'a', 'b', …, 't') ; for each valid i, the ...
0
votes
0answers
41 views
Multiple Optimal Solutions in Dynamic Programming
In 2-D dynamic programming problems like Edit Distance and binary knapsack, there can be multiple optimal solutions. By tracing back from the last element in the matrix one could trace out all the ...
0
votes
0answers
39 views
Matrix chain multiplication using dynamic programming
Consider we need to solve the Matrix chain multiplication using dynamic programming for this problem :
The table for min. cost is shown below :
Edit : Reference https://www.radford.edu/~nokie/...
1
vote
1answer
68 views
interval scheduling variant: 1 machine with 2 tasks need to complete only
I am looking for an optimal solution of an interval scheduling variant.
Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum ...
0
votes
1answer
50 views
Simple pathes in an acyclic graph
How to answer on many requests by type:
Count amount simple paths passing through chosen edge in an acyclic undirected graph using dynamic programming?
0
votes
1answer
79 views
Minimal number of changes to make string into concatenation of $k$ palindromes
The following question is taken from leetcode: 1278. Palindrome Partitioning III
You are given a string $s$ containing lowercase letters and an integer $k$. You need to:
First, change some ...
1
vote
1answer
37 views
Longest subarray with at most two different values - Runtime complexity for a DP solution
Consider the problem of finding, for a given input array, the longest subarray with at most two different values.
For example:
...
1
vote
1answer
61 views
Partition the indices of 2d array to minimize sum of sub-matrices
Given an $n\times n$ Matrix $M$, and the indices $[{1,2,3,4,...,n}]$ are divided into several intervals : $[1,x_1],[x_1,x_2],...[x_k,n]$, which further extract several squared sub-matrices along the $...
0
votes
1answer
58 views
Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria
You have to find out the number of good strings of length N characters in size which you can make using characters A B and C.
A string is a good String if it satisfies the following three criteria:
...
1
vote
1answer
82 views
Number of sequnces with given value
Consider a valid string with bitwise operations (AND, OR, XOR), and also placeholders $X$, where each $X$ stands for an arbitrary number from $\{0,1\}$. There are $n$ many $X$s, so there are $2^n$ ...
3
votes
1answer
98 views
Dynamic Program to solve an NP-complete partitioning problem
I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!
Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{...
1
vote
1answer
37 views
Maximize rental income given a set of date intervals
Suppose you have 1 room that you want to rent out. (AirBnb style) You want to maximize profits that you will get by renting it out.
For example:
Given intervals: ...
0
votes
1answer
137 views
Can I find all the common subsequences between 2 sequences by using dynamic programming?
I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one.
Thank you.
0
votes
2answers
315 views
Doest sorting accept a dynamic programming solution?
Are there any known / efficient dynamic programming solutions to sorting?
I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal ...
2
votes
1answer
115 views
Knapsack-like problem with profit formula
Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once.
The ...
5
votes
4answers
502 views
3xN tiling problem with blocks of size 3x1 or 2x2
I know there are a number of different tiling problems and some of them have been discussed here:
Number of ways of tiling a 3*N board with 2*1 dominoes problem
Domino and Tromino Combined Tiling
DP ...
0
votes
1answer
134 views
Line-Breaking algorithm (minimum raggedness) where spaces can have width different than 1.0
The Divide & Conquer Algorithm for Line-Breaking described here is given below, both in Python and in Dart (which is similar to Java/C#).
Line-breaking is also known as "line wrap", "word wrap", ...
1
vote
1answer
47 views
Is it possible to find a supersequence of a single array?
In Jeff Erickson's Algorithms textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest
oscillating supersequence of an arbitrary ...
2
votes
1answer
95 views
Dynamic programming problem
our uni is closed because of the COVID-19 and I'm trying to homelearn dynamic programming.
In our algorithms book, there is the following problem: (an example problem for dynamic programming)
A ...
2
votes
1answer
96 views
LaTex Text Justification badness penalty
I had been going through dynamic programming concepts and happened to read about text justification problem in which the spaces to the right of the line end are penalized with cubic times the number ...
0
votes
1answer
89 views
Is there a faster than O(n^2) solution for Box stacking problem?
The Box Stacking problem is as follows:
You are given a set of $n$ types of rectangular 3-D boxes, where the
$i^{th}$ box has height $h_i$, width $w_i$ and depth $d_i$ (all real
numbers). You ...
2
votes
1answer
669 views
Min-coin change problem with limited coins
I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
0
votes
0answers
39 views
Catching ball - finding the maximum number of caught balls
I'm attempting to solve the following problem:
Balls are falling from the sky. We know at which location (on a
straight line) will each ball drop, and we know the time (in seconds)
at which ...
2
votes
1answer
46 views
Minimum moves to “stabilize” an array
We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the ...
1
vote
3answers
621 views
Give an efficient dynamic programming algorithm that decides if a string is an interleaving of two other strings
I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book.
You’re consulting for a group of people (who would prefer not to be
mentioned here ...
0
votes
1answer
143 views
Cover interval with minimum sum intervals - DP recursion depth problem
READ ME FIRST:
I have just found the official solutions online (have been looking for them for a while, but after posting this I quickly found it), and I'm currently trying to understand it. As I can ...
0
votes
1answer
47 views
Expected number of coins
Alice and bob play a game.
Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$ green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob.
...
1
vote
1answer
40 views
Amount of k-partitions of a number
I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions.
...
1
vote
0answers
27 views
Algorithm to minimize the damage received from the monsters [duplicate]
I have been puzzled by the following question on an exam for quite a while: given a set of monsters with their health and attack damage (per second), design an algorithm that minimizes your overall ...
0
votes
1answer
44 views
Implementing Dynamic Programming Solutions
I know there alot of questions on Dynamic Programming and I feel I have a handle on the theory, use the answers from sub problems to answer the current problem, without the redundancy of recursion. ...
2
votes
2answers
613 views
Count number of pairs of elements whose product is a perfect square
Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a ...
0
votes
1answer
47 views
Minimum total waiting time for arrivals/durations
I have come up with the following problem, and cannot seem to find an effective way of solving it:
Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration ...
2
votes
0answers
23 views
Optimal strategy for tossing three dependent coins
Suppose that I have three correlated coins. The marginal probability of Head of coin $i$ is denoted by $p_i$.
The conditional probability of head for coin $i$ given the outcomes of coin $j$ and $k$ ...
0
votes
1answer
38 views
Maximun distance that can be reached [duplicate]
A stone is located at the point (0,0) of an infinite grid. The stone has exactly $n$ possible moves, not necessarily unique, each described by a $vector$ of integer coordinates. The stone can make ...
6
votes
1answer
377 views
How to extend Bellman-Ford to solve the $k$ shortest path routing?
Browsing the wikipedia I got to this page where it is said:
Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
-2
votes
1answer
46 views
Number of ways to cover 3xN board [closed]
Given a 3xN board. Find the number of ways to cover it using 2x2 or 3x1 or 1x3 tiles.
0
votes
1answer
66 views
Counting strings with balanced substrings
Consider a string of characters $a, b, c$ only. Such a string is called good if the number of $a$'s + number of $b$'s is equal to the number of $c$'s.
Given an integer $n$, find the number of strings ...
2
votes
0answers
45 views
Algebraic Dynamic Programming breakdown of a simple problem (e.g. climbing staircase)
I found recently about Algebraic Dynamic Programming. As I understand, it's a formalization that immensely simplifies developing solutions for DP problems.
I spent a few days trying to grok it, to no ...
4
votes
2answers
216 views
How can you compute the expected edit distance in $O(2^{3n/2})$ time?
In a coding challenge an answer claimed to be able to compute the expected edit distance between two binary strings of length $n$ in $O(2^{3n/2})$ edit distance calculations by dynamic programming. A ...
4
votes
2answers
306 views
Thought process to solve tree based Dynamic Programming problems
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
0
votes
1answer
102 views
Dynamic programming
Got a question and can't manage to find an answer, so help will be appreciated.
I should design an algorithm, using dinamic programming, that gets as an input a matrix, named A, with n rows and k ...
1
vote
1answer
192 views
Maximum number of similar groups of a given size that can be made from a given array
I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$.
I need to find the maximum number of groups with the ...
5
votes
1answer
254 views
Find if there is matrix that satisfying the following conditions
Given a matrix $A_{n\times n} = \{a_{ij}\}$ such that $a_{ij}$ is a non-negative number and given 2 vectors $(r_1,r_2,...,r_n)$ , $(c_1,c_2,...,c_n)$ such that $r_i,c_i\in \mathbb{Z}$ define an ...
0
votes
0answers
221 views
What are some variants of the rod cutting problem?
I am looking at the possible implementations for solving the rod cutting problem (CLRS). Do you know of any variants of this problem and their use in industry?
0
votes
2answers
856 views
min vertex cover to access k edges in a tree
I need to find the minimum number out of $N$ vertices on a tree with $N-1$ edges, so that at least $K$ edges of that tree are connected to these vertices.
For example, if $N=9$ and $K=6$ and we have ...
4
votes
1answer
175 views
Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring ...
