Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
616
questions
0
votes
0answers
13 views
0/1 Knapsack in bottom up approach [closed]
I've tried the Recursive, Memoization and DP-Top-Down approach of Knapsack problem. But not able to restructure the code for DP-Bottom-Up approach. Below is my code, its only working for fewer inputs.
...
1
vote
1answer
25 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
79 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
43 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
0answers
28 views
Is there a faster than O(n^2) solution for Box stacking problem?
Is there a faster than O(n^2) solution for the Box stacking problem?
-1
votes
0answers
23 views
How to approach weighted job/interval scheduling problem with 2 machines (dynamic programming)
Given N jobs where every job is represented by the following: Start Time, Finish Time and Value Associated (>= 0) and two machines that can do the jobs,
The goal is to find the maximum value subset ...
2
votes
1answer
55 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 ...
-1
votes
0answers
22 views
The average number of dominos
Consider there are $n$ dominos to be placed in a lone (such as "DDDDD", where D is dominos). While placing dominos, they may fall to their right or left, making other dominos in line to fall down. ...
0
votes
0answers
31 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
29 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 ...
0
votes
1answer
54 views
Give an efficient Dynamic programming algorithm that takes strings s,x, and y and decides if s is an interleaving of x and y
I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book. Not a homework
You’re consulting for a group of people (who would prefer not to be
...
0
votes
1answer
27 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
41 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
37 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
24 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
37 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
385 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
24 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
21 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
25 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 ...
3
votes
0answers
84 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
42 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
45 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
42 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
198 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 ...
3
votes
2answers
138 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
66 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
45 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
251 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
49 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
0answers
46 views
A variant of the knapsack problem
Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
1
vote
2answers
763 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 ...
3
votes
1answer
116 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 ...
0
votes
0answers
29 views
Schedule a Seminar in Minimum Time
There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
3
votes
1answer
101 views
Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1
So if $k = 3$ and $n = 2$ and we select the element $a_1[3]$ of the first array then we have to select $a_2[1]$ from the second array. If we select the element $a_1[2]$ then also $a_2[2]$ must be ...
2
votes
1answer
61 views
(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?
The following question is taken from Leetcode entitled 'Combination Sum'
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique ...
1
vote
1answer
241 views
Counting number of paths between two vertices in a DAG
I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
1
vote
0answers
53 views
Optimal ordering - Dynamic programming on subsets
We have a set T of n elements and m subsets $R_i \subset T i = 1,...,m$.
The $S_i$ are not assumed to be different. We also define an ordering of T, a one-to-one mapping $\pi$ of $T$ onto the set of ...
1
vote
0answers
20 views
Dynamic programming for subsequence metric
Let $a = a_1, \ldots, a_n, b = b_1, \ldots, b_m$ be sequences of positive integers and for any respective subsequence of length $k$, we consider $\sum_{i=1}^k (a_{x_{i}}-b_{y_{i}})^2$. Given a bound $...
1
vote
1answer
134 views
longest palindromic subsequence / substring and dynamic programming
The longest palindromic subsequence problem can be solved using dynamic programming because it is recursive and has overlapping subproblems, as described in https://www.geeksforgeeks.org/longest-...
0
votes
2answers
237 views
Why this greedy algorithm fails in rod cutting problem?
Recall the rod cutting problem.
Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and ...
0
votes
0answers
88 views
Minimizing the distance from a set of nodes in a tree
We have a binary tree with n nodes and a number k which signifies the number of nodes that we put on a set. What is the optimal algorithm to select a set consisting of k nodes, that minimizes the ...
2
votes
1answer
32 views
How does a dual core microprocessors run so many programs?
I have a laptop with Intel dual core and it runs, the OS windows, and many application from Opera, age of empires, word, excel etc open at once just fine. If it only has 2 cores, how can so many ...
1
vote
0answers
45 views
Egg dropping problem binomial coefficient recursive solution
I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors)
In the binomial coefficient solution we construct a function $f(x,n)$, ...
4
votes
0answers
75 views
Assign n people to m rooms of different sizes, such that noone is alone
I'm looking for an efficient way to assign n people to m rooms in a very specific way.
INPUT:
The program receives two sets of people (set of males and set of females), as well as a set of available ...
1
vote
1answer
151 views
Selecting elements from two arrays to get a target sum
Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer.
Design an algorithm to solve the following problem.
For each index $i$ ($1\leq i \leq n$)...
3
votes
1answer
136 views
Is dynamic programming restricted to optimization problems?
The usual criteria used to decide if a problem can be solved using dynamic programming is (1) if it has optimal sub-problems and (2) if it has overlapping sub-problems. Does the word "optimal" mean ...
5
votes
0answers
79 views
Find the 'best' longest common subsequence
I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and ...
2
votes
1answer
63 views
Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$
For example $46$ is a perfect number , since $4+6=10$ . If $n=1$ , answer is $19$. If $n=2$ , answer is $28$. If $n=3$ , answer is $37$ and so on .We need to make a program which takes $n$ and ...
1
vote
0answers
39 views
Weighted Activity Selection Problem with allowing shifting starting time
I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists.
In my case, I am allowed to ...
