# Questions tagged [dynamic-programming]

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

26 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
663 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 ...
439 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 ...
130 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: ...
50 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. ...
451 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 ...
88 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 ...
172 views

### Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
206 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 ...
839 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 <...
41 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 ...
1k views

### minimum window subsequence leetcode dynamic programming solution

Given strings S and T, find the minimum (contiguous) substring W of ...
652 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 ...
1k 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 (...
330 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 ...
536 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 ...
47 views

### How do I optimize memoization in order to find longest palindromic substring?

I want to find the longest palindromic substring using dynamic programming in Python3. The strings can be as large as this string. I have seen other questions on this problem that successfully solve ...
304 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. ...
71 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 ...
321 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 ...
168 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. ...
3k 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 ...
302 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: ...
96 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 ...
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 ...