# Questions tagged [dynamic-programming]

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

783 questions
Filter by
Sorted by
Tagged with
127 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 ...
56 views

### speed up straightforward solution using dynamic programming

i recently got onto the following problem: we consider the following array: A = [2, 3, 6, 1, 6, 4, 12, 24] we need to count the number of times these two ...
114 views

### How to derive max amount of items from DP table of Knapsack problem?

I have a little bit changed algorithm for 1-0 Knapsack problem. It calculates max count (which we can put to the knapsack) as well. I'm using it to find max subset sum which <= target sum. For ...
39 views

### Is top-down dynamic programming always recursive?

I think top-down dynamic programming is mostly recursive. For instance, solving the rod-cutting problem by this algorithm: ...
71 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 ...
56 views

### Proving existence of an optimal substructure for the DP problem "Sherlock and Cost" from HackerRank

Problem statement from HackerRank ( source: https://www.hackerrank.com/challenges/sherlock-and-cost/problem ) : In this challenge, you will be given an array $B$ and must determine an array $A$ ....
34 views

### Proving existence of an optimal substructure for the DP problem "Equal" from HackerRank

Q: How one would prove the existence of an optimal substructure for the following DP problem "Equal" from HackerRank? Problem statement: My attempt: Let $A = [ a_1,a_2,...,a_n ]$ be our ...
331 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-...
1k 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 ...
47 views

### Time Complexity of Memoized Solution

I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
43 views

### Dynamic Programming: What is a subproblem space? Why do we need varying indexes to characterize a subproblem?

In dynamic programming: 1. what is the definition of the space of subproblems? does it have a mathematical definition? 2. why is it necessary to have an arbitrary index for the subproblem to vary? To ...
188 views

### Count the possible plans for nurses

I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below: The director of a hospital want to schedule a working plan for a nurse in a given period of N ...
67 views

### Algorithm to Check for Upper Bound of Levenshtein Distance

I am looking for an algorithm that checks if the Levenshtein distance between two strings $s_1$ and $s_2$ is less than a certain upper bound $B$. I know, there are plenty of algorithms for calculating ...
956 views

### When not to use dynamic programming

I was reading about dynamic programming and I understood that we should not be using dynamic programming approach if the optimal solution of a problem does not contain the optimal solution of the ...
55 views

### Two-Sum - Range Allowance Algorithm Design

🧩 What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity? Optimize for runtime over memory complexity. ...
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 ...
38 views

### What are the reasons for solution assumptions behind the longest subsequence problem?

All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L[i] be the length of the LIS ending at index i...": ...
1k views

### Technique for converting recursive DP to iterative DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
465 views

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

### Given a set of integers and target, find all subsets of size k such that sum of elements of each subset equals target

I am trying to solve below problem Given a set of integers A, and target integer, find all subsets of size k such that sum of elements of subset equals target. One approach could be enumerating all ...
577 views

### Counting Total Number of Non-Equivalent Configurations in a 2-D Grid

This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both. Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ ...
1k views

### Prove Recursive formula (Dynamic programming) N(C,i)

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
35 views

### How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?

I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
73 views

### Sub-exponential time algorithm to compute playoff chances

There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the ...
73 views

### Applying subproblem technique to permutations with grouping

I am trying to apply overlapping subproblems and dynamic programming to permutations. Say, we have a set of $n$ elements in a string. Each of these elements could be a $1$ or a $0$. Given some ...
780 views

### Print (not count) all possible path classic climbing stair problem)

I came across this classic question and found may many solution to it. for loop and DP/ reclusive + memorization. Also found a twisted version of the questions asking to print all possible path ...
57 views

### Unconstrained subset sum vs constrained subset sum?

In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by. Question 1: ...
5k views

### Inventory planning problem solved through dynamic programming

I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed). 15-11: Inventory Planning, p.411 The Rinky Dink Company makes machines that resurface ice rinks. The ...
21 views

### Minimum weight $k-$path cover on a DAG proof verification

Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
31 views

### Is weighted interval scheduling where the weights are the interval lengths simpler/faster

In weighted interval scheduling arbitrary weights are given to the intervals. A clean dynamic programming solution runs in $O(n \log n)$ time. If the weights of the intervals are their integer lengths,...
69 views

51 views