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.

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\$....
CyberLingo's user avatar
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 ...
voithos's user avatar
  • 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 ...
txizzle's user avatar
  • 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 ...
CyberLingo's user avatar
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 ...
gcbenison's user avatar
  • 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: <...
gaazkam's user avatar
  • 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: ...
loremIpsum1771's user avatar
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: ...
Sidharth Samant's user avatar
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 ...
MAG's user avatar
  • 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 ...
Justin's user avatar
  • 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 ...
Suraj Palwe's user avatar
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 ...
user avatar
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, <...
Lin Ma's user avatar
  • 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 ...
Martin Boros's user avatar
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 ...
JavaDeveloper's user avatar
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. <...
NinjaG's user avatar
  • 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 ...
Lin Ma's user avatar
  • 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)\$ ...
coderodde's user avatar
  • 28.7k