Skip to main content

# Questions tagged [dynamic-programming]

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

18 questions
Filter by
Sorted by
Tagged with
11 votes
3 answers
3k 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$....
• 449
58 votes
3 answers
69k views

### Dynamic programming knapsack solution

I wrote a solution to the Knapsack problem in Python, using a bottom-up dynamic programming algorithm. It correctly computes the optimal value, given a list of items with values and weights, and a ...
• 862
10 votes
3 answers
4k 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 ...
• 203
8 votes
2 answers
248 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 ...
• 449
7 votes
4 answers
8k views

### Python implementation of the longest increasing subsequence

Prompted by this question on Stack Overflow, I wrote an implementation in Python of the longest increasing subsequence problem. In a nutshell, the problem is: given a sequence of numbers, remove the ...
• 347
6 votes
2 answers
816 views

### UVA 100: "The 3n + 1 problem"

I’ve solved UVA Problem 100: The 3n + 1 problem . In short, the task was to write a program that calculates a maximum of Collatz sequence lengths for any given range of starting values. My program: <...
• 561
5 votes
3 answers
2k views

### Find smallest number of squares that sum to a number

Leetcode problem 279 “Perfect Squares” is: Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) I wrote the following solution: ...
5 votes
2 answers
1k views

### High execution time of LCS length program in Python2

I was trying to solve the Longest Common Subsequence problem on a HackerRank exercise. It's quite simple and straightforward, just print out the length of the LCS. I submitted this code: ...
5 votes
2 answers
598 views

### Edit distance implementation

This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: In order to transform one source string ...
• 2,934
4 votes
1 answer
627 views

### The Dungeon game

This is a Leetcode problem - The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our ...
• 2,489
4 votes
3 answers
13k 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 ...
• 161
4 votes
5 answers
802 views

### Find maximum value of recursively-defined "fusc" function

I've been trying this question from SPOJ, which asks for the user to enter a number n, and they will receive a maximum fusc value that lies in between 0 to ...
4 votes
1 answer
431 views

### Different path for grid move

Given a m * n grids, and one is allowed to move up or right, find the different number of paths between two grid points. My major idea is, if move r steps right, <...
• 3,453
3 votes
1 answer
313 views

### Efficiently calculate value of Pascal's Triangle using memoization and recursion

So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values ...
• 133
3 votes
1 answer
4k views

### Jump game in Java

Looking for code review, suggestions for improvement, best practices etc. The problem definiton is Jump Game Given an array start from the first element and reach the last by jumping. The ...
• 8,391
3 votes
1 answer
2k views

### Coin sum dynamic programming in Python

I am preparing for an interview, and here's a popular problem on the dynamic programming. And I want to see if there's any feedback or code review for my solution at dynamic programming question. <...
• 2,469
3 votes
1 answer
246 views

### Dynamic programming solution for cross river algorithm (part 2)

I'm working on the cross river problem (previous post here). Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style advice is appreciated. More ...
• 3,453
2 votes
1 answer
411 views

### An iterator returning all possible solutions to n-queen problem in Java - follow-up

(See the initial iteration.) Now I have slightly improved performance of the iterator. Whenever we have set a queen at a particular board cell, the previous iteration sacrifices $\mathcal{O}(n)$ ...
• 28.7k