Questions tagged [dynamic-programming]

Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

Filter by
Sorted by
Tagged with
0
votes
1answer
17 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 ...
-1
votes
0answers
42 views
+50

How can this Line-Breaking algorithm consider spaces as having 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", ...
0
votes
0answers
9 views

Why some website I cannot open? [closed]

I try to open many time this site this link: https://uopeople.influitive.com/users/sign_in however something wrong. This is what it says, This page isn’t workingambassadors.uopeople.edu redirected you ...
2
votes
1answer
19 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 ...
2
votes
2answers
75 views

3xN tiling problem with 3x1 vertical and horizontal + 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 ...
2
votes
2answers
943 views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
-1
votes
0answers
24 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. ...
4
votes
4answers
7k views

Dynamic Programming vs Memoization

I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization. Am I ...
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 ...
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
1answer
81 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
46 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
31 views
-1
votes
0answers
24 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
57 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 ...
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
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 ...
0
votes
1answer
56 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 ...
2
votes
2answers
99 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. ...
7
votes
1answer
270 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x \alpha(x)V(x)\\...
0
votes
1answer
31 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
42 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 ...
3
votes
1answer
118 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 ...
2
votes
2answers
409 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
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 ...
5
votes
1answer
625 views

Find equidistant triplets in a tree

Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between ...
0
votes
1answer
28 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
85 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
2answers
131 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 ...
4
votes
2answers
200 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 ...
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 ...
3
votes
2answers
140 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 ...
2
votes
1answer
47 views

Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
1
vote
1answer
140 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-...
1
vote
1answer
866 views

Printing actual solutions for the coin exchange problem

As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight ...
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
59 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?
1
vote
2answers
767 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 ...
1
vote
1answer
61 views

Optimizing the problem

I have a recurrence relation: $$f(a,b) = \begin{cases} 1 & (a,b) = (0, 0)\\ 1 & (a,b) = (a, 0)\\ 0 & (a,b) = (0, b)\\ 2a & (a,b) = (a,1)\\ f(a-1,b) + f(a-2, b-1) + f(a-1,b-1)...
2
votes
1answer
181 views

What is the optimal way to perform GCD chain operation?

Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming. Similarly ...
0
votes
0answers
47 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 ...
0
votes
2answers
4k views

Dynamic programming: Knapsack with repetition, Find the number of redundant machines

I have just started to learn Dynamic Programming, and so far I have studied the few basic concepts; longest common subsequent problem, edit distance problem and the knapsack problem. I have attempted ...
2
votes
1answer
229 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...

1
2 3 4 5
13