# Questions tagged [dynamic-programming]

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

14 questions
Filter by
Sorted by
Tagged with
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$....
65k 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 ...
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 ...
353 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, <...
212 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 ...
7k 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 ...
216 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 ...
583 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: <...
1k 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: ...
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: ...
397 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 ...
7k 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 ...