# Questions tagged [dynamic-programming]

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

221 questions
Filter by
Sorted by
Tagged with
752 views

### Pass Triangle challenge

In order to solve this challenge: Challenge Description By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27. <...
596 views

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 ...
609 views

### Quick Sum TopCoder (Brute Force solution)

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the ...
291 views

### Counting paths in an n-dimensional grid that stay within the boundaries

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 ...
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 ...
3k views

### Find the Nth number divisible by only 2,3,5, or 7

I recently participated in a small friendly competition and this was one of the questions: A number whose only prime factors are 2, 3, 5 or 7 is called a humble number. The first 20 humble ...
2k views

### Implementation of Longest Common Subsequence

So I implemented the LCS algorithm once using a 2-D matrix to store values while the other one used a python dictionary. I found the dictionary implementation was easier to implement and was a more ...
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 ...
79 views

### Construct biggest stacked tower with restriction

Problem The problem is to build the tallest tower made up of cylinders, respecting all the rules. Will be arranged on the table, an amount of $N$ cylinders. Each cylinder has one color: Red, ...
1k views

### Subset sum whose set contains only positive integers

I was trying to write a dynamic programming algorithm using a bottom up approach that solves the subset sum problem's version where the solution can be either an empty set and the initial set can only ...
2k views

### Finding the rod pieces in the rod cut issue

I have been reading the chapter 15 of "Introduction to Algorithms" (3rd edition) by Cormen, etc. The chapter 15 is about dynamic programming, and the first example they show us is the "rod cut problem"...
733 views

### LeetCode Minimum Path Sum algorithm

I am attempting to solve the Minimum Path Sum algorithm problem and I have a working solution, however there was an unwritten requirement that the algorithm not exceed an unspecified amount of time ...
1k views

### HackerRank - Candies

Here is the solution I've written for Hacker Rank Candies challenge. It uses dynamic programming (memoization in a boxed array). I'm interested on what could be done to improve this code in term of ...
5k views

### Calculating the sum of array elements to the left and right

I am using C++ to code the following logic: An Array is given we have to traverse the array such that sum of array elements to its left must be equal to sum of elements to its right. BTW this is ...
447 views

### ChessMetric - Topcoder Challenge

My solution for the topcoder ChessMetric challenge seems really slow. I feel like there should be a better way, but I'm not sure. Challenge Description Suppose you had an n by n chess board ...
295 views

I'm learning Dynamic Programming, following the topcoder guide. I just solved the AvoidRoads challenge. It passes all the test cases, but I don't have much experience, so I don't know if it's good. ...
208 views

### Minimum number of coins problem using dynamic programming - follow up

I previously posted a code here. It turns out that the code is not following the correct dynamic programming principles and instead it was based on a greedy approach. Hence, I started again, keeping ...
2k views

### Coin Change: Minimum number of coins

Problem: You are given n types of coin denominations of values $v(1) < v(2) < ... < v(n)$ (all integers). Assume $v(1) = 1$, so you can always make change for any amount of money $C$....
531 views

I'm learning Dynamic Programming, following the topcoder guide. I just solved the BadNeighbors puzzle. It passes all the test cases, but I don't have much experience, so I don't know if it's good. ...
157 views

### Max contiguous slice in Ruby

I need to compute the max contiguous slice in an array. I wrote this function, but I am not sure if it is correct or I am missing edge cases. I ran several cases. ...
6k views

### Implementation of Sequence Alignment in C++

Below is my implementation of the dynamic programming solution to the sequence alignment problem in C++11: ...
2k views

### DP example for “Power of Two” in Python

I'm not familiar with Python but want to provide a code snippet for an SO question about Dynamic Programming. The snippet should show the bottom-up approach of DP. The function ...
1k views

### House-coloring optimization challenge

I have an interview coming up in the next few weeks, and I'm choosing to be interviewed in Python. I began programming in Python (it was about four years ago), so the syntax is natural to me, but I ...
260 views

### Undo format when format disappears

I was posed a question as follows: Given a sentence like "John is a bad man", lets say all the formatting disappears and you are left with one string "johnisabadman". Given a dictionary of words, ...
3k views

### Longest Increasing Subsequence

I am learning dynamic programming and I have written down some code for longest increasing subsequence. I would like to know if there is any case or any area of improvement in the terms of ...
1k views

### Counting Increasing Subsequences of size K recursive

The original description of the problem can be found here, its input here and its expected output here. The problem: Given a integer sequence a1 ... an (-10000 $\leq$ ai $\leq$ 10000). Where ...
8k views

### Find the minimum number of coins

I'm trying to learn dynamic programming and the most popular one is to find the minimum number of coins for the change. I come up with this but I just want to improve this code which I think it could ...
96 views

### Optimal way to annihilate a list by removing items from the ends

I'm stuck with a contest problem. Description: What is the minimum number of moves to annihilate an int array where the possible moves are: Remove both the first and last elements if they are equal ...
5k views

### Finding all the subsets in an array of integers that sum to a given target

Problem Statement: Given an Array if ints, Find out all the subsets in the Array that sum to a given target value. Example: If the input array is: ...
2k views

### Minimum number of coins - (dynamic programming solution - topdown approach)

This is a problem from topcoder tutorials Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many ...
160 views

### Reading, processing and counting an array setting limits

Last weekend my teacher asked me to create code to solve a problem: Giving a dynamic array, we want to pass the array elements from a file. The first number in the file N gives us the array length. ...
2k views

### Solving the rod-cutting problem using dynamic programming

I've written what I believe is a valid dynamic programming solution to a variation of the rod cutting problem. In this problem, the goal is to make as few cuts as possible on a rod of length n. I ...
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 ...
758 views

### Optimizing a dynamic programming solution for “Oil Well”

I'm trying to solve the Oil Well problem on Hackerrank using dynamic programming and it works. However, it times out for some of the test cases. I wanted to know how this program can be improved so ...
1k views

### Coin problem through brute force

I have some code that will brute force solve the following problem: Given a set of x coins and a target sum to reach, what is the fewest number of coins required to reach that target? The code so ...
3k views

### Project Euler #14 — longest Collatz sequence

I was reading this question and realized that I didn't know Python well enough to critique the algorithm. So I wrote a Java solution instead, which is inappropriate for that question. Since there's ...
1k views

### Calculate possible balances in piggy-bank by weight

I have solved Piggy-Bank problem on SPOJ using dynamic programming. The question asks you to get the minimum value that is possible with given weight ($w$) and one or more coins ($n$) with given ...
827 views

### Word break problem with dynamic programming

This is the original question. I have implemented it in both ways. If I enter the word "icecream", should I output "ice" "cream" and also "icecream", or just "ice" and "cream"? Is this a good ...
205 views

### Memoization for calculating minimal traversal distance within a positive matrix

The code below is for calculating the minimal traversing distance from the top left point of the matrix to the bottom right point of the matrix. GitHub Here is the core functionality. Please note ...
447 views

### Google CodeJam Round D APAC Test

Problem A: Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the ...
756 views

### Dynamic Programming for printing additive numbers up to digits n

Edit: I am hoping to get some review / make sure I am understanding dynamic programming correctly. I am trying to print out all additive numbers up to digits n using dynamic programming. Additive ...
683 views

### Longest Common Subsequence and Longest Subsequence Palindrome

The following code computes: The longest common subsequence between two strings, where a subsequence of a sequence does not have to consist of contiguous elements of the sequence. The longest ...
453 views

### Handling shared state among a lot of elements in Angular

I am working on a project in Angular where I have a number of similar data objects. When you click on anyone of them it's state and amount of data shown will change. All of the objects start in the ...
4k views

### Longest collatz sequence using dynamic programming

I am trying to solve longest collatz sequence problem under 1000000 with the below code. Can anyone suggest a faster way to approach this problem? I was thinking of dynamic programming, but I'm ...
3k views

### Project Euler 81 (minimum path sum through a matrix)

Problem Statement: In the 5 by 5 matrix below, 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331 ...
2k views

### Substitution cipher algorithm performance boost

This algorithm is meant to read a string of numbers on an input, a naive substitution cipher code (A = 1, B = 2, ..., Z = 26) and output the number of ways the code could be interpreted (e.g. 25114 ...
Question Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next $N$ days. Each ...