# Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

27 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
634 views

### Multiple 0-1 knapsack

I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs. Input description The first input line consists of two positive integers N e ...
85 views

### Python program to solve matrix-chain multiplication

An assignment at school required me to write a Python program for this task: In the matrix-chain multiplication problem, we are given a sequence of matrices ...
120 views

### Convert top-down subset sum to bottom-up

I have written the code for calculating subset-sum and also printing the first encountered non-empty subset from the left that sums up to the given sum. My code in Java is as follows: ...
323 views

### Hackerrank: Sherlock and anagram (optimal time complexity)

Problem statement Given a string $S$, find the number of "unordered anagrammatic pairs" of substrings. Input Format First line contains $T$, the number of testcases. Each testcase ...
83 views

### Uses subproblems to solve large problem (maximization of value within space)

If this question is not a good question for this board, I will remove it. I am looking for ideas on how I could improve the code as I am a beginner trying to learn how to program. Here I have a ...
61 views

### Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
115 views

### Smith-Waterman algorithm for local sequence alignment with affine gap penalties

The following is a summary from the top of my head so please correct me if I'm wrong. See the Wikipedia article for more. This is about determining the (score / edit distance of the) most similar ...
445 views

### Robot on a Grid: Find a path between two corners with forbidden cells on the road

Problem statement The problem is defined in the book as following: 8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and <...
192 views

### Check the equality for each subset of a string S against the target T and return a count

I wrote the following code to solve this leetcode problem: ...
34 views

### Optimizations for Knapsack with 3 dimensions

Problem Statement: I am given a set of prices for $n$ items I have to find out what is the maximum value I can get with $M$ money by selecting exactly $C$ items without exceeding the amount of ...
841 views

### minimum window subsequence leetcode dynamic programming solution

Given strings S and T, find the minimum (contiguous) substring W of ...
46 views

### Number of ways to complete a plan

I worked on a dynamic programming problem. Here is its link. I have to find the number of ways respecting the constraint that user doesn't go to the Gym for two consecutive days. ...
535 views

### Hackerrank: Max Score

Problem statement Consider an n-element sequence of integers, A = {a0, a0, ..., an-1}. We want to perform $n$ operations on $A$, where each operation is defined by the following sequence of ...
670 views

### Word Wrap via Dynamic Programming

Word Wrap problem in short: Given n words and a line length, break the words into lines in such a manner that minimizes the sum of the costs of all the lines. Consider the cost of each line being (...
306 views

### Shortest bitonic tour

This a solution to the shortest bitonic tour using dynamic programming. Bitonic tour starts at the leftmost point then goes strictly rightward to the rightmost point and finally strictly leftward to ...
486 views

### Recursive implementation of integer partition without re-arrangement

Problem: Integer partition without re-arrangement Input: An arrangement S of nonnegative numbers {s1, . . . , sn} and an integer ...
40 views

### Hackerrank Beautiful Strings

Problem Statement You are given a string, S , consisting of lowercase English letters. A string is beautiful with respect S to if it can be derived from S by removing exactly 2 characters. ...
64 views

### selecting 5 best players out of 2 team

Let us assume that we need to develop an application which can select best 11 players to score maximum points. The application will select the best players after completion of a match. The rules are ...
250 views

Ada the Ladybug has several coins in her wallet. She is wondering, how many different values [sum of some subset of coins] is she able to make (in given range). Input The first line contains two ...
154 views

THIS is the link to the problem on SPOJ. I thought it would be better to give the link to the problem instead of me trying to explain as the question is not very clear at first sight. I was able to ...
126 views

### x as the sum of unique integers raised to power n

I've done this problem using recursion. But I'm not sure that could this be optimized for bigger values of x using memoization. ...
2k views

### Traceback in sequence alignment with affine gap penalty (Needleman-Wunsch)

I am working on an implementation of the Needleman-Wunsch sequence alignment algorithm in python, and I've already implemented the one that uses a linear gap penalty equation for scoring, but now I'm ...
295 views

### Longest palindrome subsequence

This algorithm finds the longest palindrome that is a subsequence of a given input string in $\Theta(n^2)$. Example Input: character Output: ...
69 views

### SPOJ Aliens in a Train

I need to find the largest interval with a value less than a limit Lt. The data is as follows: For every test case T: Number of elements N, limit Lt N number of elements data I wrote the ...
1k views

### DP algorithm to find minimum average wait for customer-serving system

Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from ...
I am trying to solve a question given on Codeforces involving dynamic programming with 3D arrays. F. Trucks and Cities There are $n$ cities along the road, which can be represented as a ...