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
0answers
41 views

Find cheapest path from 1st city to the $n$th city

The title may be a bit misleading, but this is essentially a DP problem. The problem is that we have $n$ cities labeled from $1, ... n$ and we are trying to find the cheapest way to travel from 1 to $...
0
votes
1answer
198 views

DP - Removing contiguous subsequences from a sequence optimally

I was asked this question a while ago and I'm very stuck: You have a sequence of 0's and 1's, and you can perform one ...
0
votes
0answers
24 views

How to apply recursion in this problem [duplicate]

Problem Statement : You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,...DN). In one step, you can walk one step ahead or behind in any one ...
0
votes
0answers
323 views

Proving a dynamic programming recurrence for coin exchange correct

Suppose I have $n$ kinds of coins $c_1, c_2, \dots, c_n$. I'm given: $S$, an amount of money I should construct with minimum number of coins. I came into the following formula: $$ T(n,S) = \begin{...
0
votes
0answers
236 views

Weighted Interval Scheduling with constraint

How do we solve the weighted interval scheduling problem if given a maximum weight? I understand the solution for the problem when we are simply interested in the maximum weight possible, but how do ...
0
votes
0answers
587 views

Dynamic programming for counting knapsack solutions

Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I ...
0
votes
0answers
854 views

Dynamically weighted priority queue?

Elements are stored in a single dynamic data-structure $D$ Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$ The function $f$ is weighting based on the value of ...
0
votes
1answer
132 views

Count the number of integers satisfying two conditions using DP

Given two integers $n$ and $m$, how many numbers exist such that all integers have all digits from $0$ to $n-1$, the difference between two adjacent digits is exactly $1$, and the number of digits in ...
0
votes
2answers
5k 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 ...
0
votes
1answer
725 views

Knapsack problem with the restriction on the number of items

Suppose $X$ is a set of integers. I am interested in the algorithm which computes the number of ways to represent an integer $W$ as a sum of exactly $k$ elements from $X$. Is it possible to modify the ...
0
votes
1answer
2k views

Is there Any difference between dynamic programming vs branch-bound vs delayed column generation

I was reading about cutting stock problem https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-...
0
votes
1answer
94 views

Can the algorithm be optimized?

I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
-1
votes
1answer
273 views

Algorithm : Visiting all stations in minimum time with additional constraints

I was given this question and not sure how to solve this. This is a DP minimization problem ? Problem : There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to ...
-1
votes
2answers
930 views

How can I write this backtracking algorithm using dynamic programming?

Problem: There are $n$ points on a map, $p_1,..p_n$. There are two officers located initially at $(0,0)$ coordinate. They want to patrol all of these points with a minimum traveling (each officer ...
-1
votes
1answer
577 views

Why do we need optimal substructure for dynamic programming?

Cormen and others in their book on algorithms in chapter "15 Dynamic Programming" repeat again and again that we need to prove that "a problem exhibits optimal substructure". A problem exhibits ...
-1
votes
1answer
569 views

Are basic CS algorithms used in machine learning?

I have read some articles which state that basic algorithms such as dynamic programming , graph algorithms etc are not required int machine learning fields such as deep learning , reinforcement ...
-1
votes
1answer
358 views

Mininun changes required in a directed graph to make path from 1 to n

i have a directed graph. Basically, i have to find how many edges i need to change to opposite direction to make a path between 1 and n. So, i tried solving it by making the graph undirected and ...
-1
votes
1answer
451 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 ...
-1
votes
1answer
655 views

Knapsack progblem with two conditions

I want to create an algorighm (with dynamic programing) similar to 1/0 knapsack problem but, I have one extra condition isVegetable or isFruit. Assume we have N food items where we know ...
-1
votes
1answer
220 views

Find biggest K, such that any subset of size less than K is not affecting the array

Let's say we have given array $A = \{a_1, a_2, a_3,\dots,a_n\}$ of size $n$, and integer $L$, we want to find biggest integer $K$, such that the array without any subset of size $x, x\leq K$ will have ...
-1
votes
1answer
396 views

Quadratic algorithm for Matrix Chain Multiplication [closed]

I have an algorithm that supposedly solves the matrix chain multiplication problem in $O(n^2)$ time. I have tested it only on trivial cases and they turned out to be correct. By no means, am I a ...
-1
votes
1answer
312 views

Dynamic Programming - Adding up N Integers

I'm studying for a final and the professor gave us a practice problem to prepare, but it's extremely difficult and I've been hacking at it for hours with no luck. Here it is: It's driving me bonkers ...
-1
votes
1answer
4k views

Dynamic Programming To calculate the combinations [closed]

This is a problem from a past contest at topcoder : Problem. Its solution is given here : Solution [Scroll Down to Penguin Emperor] I am unable to understand how the section with subheading "...
-1
votes
1answer
428 views

Regarding the height of a recursion tree on dynamic programming

I am trying to understand dynamic programming and I am watching this mit video. If you guys could take some time out , can you refer to the slide on 41:36 . Why is the height m+n. I just don't get it ...
-1
votes
0answers
16 views

Checking if the spacetime complexity is the same for top-down and bottom up approach but different for runtime

Seeking help for the below bullet points. I will like to check whether the space-time complexity for both solutions is the same. Also, the run-time complexity for both is different. Here is the ...
-1
votes
1answer
33 views

Max sum non adjacent and k size subsequence

You are given a number n, representing the count of elements. 2. You are given n numbers, representing n elements. 3. You are given an integer k. 3. You are required to find the maximum sum of a ...
-1
votes
1answer
78 views

You have K amoebas and one amoeba can divide into A,B,C amoebas after one instruction then find the minimum no. of instruction to have N amoebas

. You have developed an artificial amoeba, and you can control exactly how it divides. Each individual amoeba can be instructed to divide into A, B, or C amoebas. That is, if you instruct an amoeba to ...
-1
votes
1answer
962 views

Filling a container with boxes

I have a problem in my Algorithms Class which i am trying to solve for the past two days but I can't. I want to fully fill a container with the MINIMUM number of given boxes with dynamic programming. ...
-1
votes
1answer
205 views

To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements

This problem is from codechef.Can anyone please help me out with this one as I am unable to find out the subproblem.Thanks in advance! Problem -: In IPL 2025, the amount that each player is paid ...
-1
votes
1answer
484 views

Check if a string can be split into two subsequences

Given a string S of length N, a string A of length M, a string B of length O such that N >= M + O. Check if the string S can be split into two subsequences X and Y such that A = X and B = Y. Example: ...
-1
votes
1answer
1k views

How to balance parentheses/brackets in a string with minimum cost?

Given a word composed of opening and closing parentheses and brackets, we can do two operations: Rotate a parentheses or bracket. That is, you can replace ( for ), ) for (, [ for ] and ] for [. This ...
-1
votes
1answer
885 views

Finding number of maximum independent sets in tree, using dynamic programming

I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around. I've been ...
-1
votes
1answer
2k views

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ? for example : for n=10 1 2 3 4 10 20 30 40 100 200 the sub-sequence of length ...
-1
votes
1answer
99 views

Tour de France problem : Dynamic programming

Here is the question: You are doing the Tour de France and you are given a map with all the n places where you can refill your water bottles. Your bottles fit 2 liters of water with which are enough ...
-2
votes
1answer
88 views

Explain BadNeighbors problem statement [closed]

I was solving a problem on topcoder http://community.topcoder.com/stat?c=problem_statement&pm=2402&rd=5009 . There is one example : ...
-2
votes
1answer
72 views

Wall Climbing Dynamic program

How do i solve this? I am not sure where to start. I am trying to define a Optimum solution which i can use to create a dynamic program. I am not sure what the characteristics of the optimum should be....
-2
votes
1answer
44 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.
-2
votes
1answer
1k views

NUMBER OF WAYS TO GET XOR OF n NUMBERS TO BE 0

Alice and Bob are playing the game of Nim with $n$ piles of stones (p[0], p[1], ..., p[n-1]). If Alice plays first, she loses if and only if the 'xor sum' (or 'Nim sum') of the piles is zero, i.e. $p[...
-2
votes
1answer
356 views

Using dynamic programming to find the number ofl increasing subsequences [closed]

I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing ...
-2
votes
1answer
732 views

Algorithm to decide the Kleene Star of a Language A

Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)? Moreover, can an $O(n^2g(n))$ time ...
-2
votes
1answer
132 views

Dynamic Programming Approach

when we are trying to solve a problem with dynamic programming. we have to follow some general steps characterize the solution structure Recursively define optimal solution compute the value from ...
-2
votes
1answer
148 views

why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm

We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists. ...
-2
votes
1answer
271 views

How to calculate the minimum price required to buy all the stones?

I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)). Can someone please help me out to solve this faster?
-3
votes
1answer
1k views

How to do Fairy Chess problem in O(N^3)?

https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c88e0dec8a Fairy Chess (35 Points) You have a $N \times N$ chess board. An $S$-leaper is a chess piece which can move from ...
-3
votes
1answer
53 views

Subset sum problem with a complication

I have a sorted list of numbers. I know they can be divided into two parts. I also know the sum of those 2 parts. I want to know what these subsets are. How can i find them? The size of my list can be ...
-4
votes
1answer
263 views

Maximizing profit

Problem: Given 11 numbers {N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11} where N1:amount of profit from product A N2:amount of profit from Product B N3:amount of time ...

1
10 11 12 13
14