Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
11
votes
3answers
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\$....
51
votes
2answers
62k 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 ...
10
votes
3answers
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 ...
4
votes
1answer
336 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, <...
8
votes
2answers
211 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 ...
7
votes
4answers
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 ...
3
votes
1answer
204 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 ...
6
votes
2answers
540 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: <...
5
votes
2answers
835 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: ...
4
votes
2answers
383 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 ...
4
votes
3answers
6k 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 ...
2
votes
1answer
362 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
votes
1answer
3k 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 ...