Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
297 questions
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
14
votes
5
answers
3k
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 ...
- 486
12
votes
5
answers
7k
views
Dynamic programming with Fibonacci
I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code.
...
- 665
12
votes
2
answers
640
views
Dynamic Programming: Fibonacci-like recurrence relation
This is a problem from my Introduction to Algorithms textbook.
Consider the infinite sequence of numbers An|n>0 = (1,1,3,4,8,11,...) defined recursively as follows.
$$
A_n = \left\{\begin{aligned}
&...
- 9,839
12
votes
1
answer
441
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 any ...
- 231
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
11
votes
3
answers
1k
views
Optimizing "Herd Sums" problem using dynamic programming
I'm trying to solve a practice problem and all is well except for the last 2 inputs my solution is too slow. Just one loop is slowing it down I think.
Herd Sums
Execution Time Limit: 2 seconds
...
- 213
11
votes
3
answers
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 ...
- 305
11
votes
1
answer
2k
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 ...
- 213
11
votes
1
answer
198
views
Loading Data Warehouse with Dynamic SQL
For a data warehousing project I ran into the following:
Custom fields that users can create, modify and delete, that should be loaded into the data warehouse as they are when the ETL happens.
On ...
- 211
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 numbers ...
- 203
10
votes
2
answers
300
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, ...
- 1,213
10
votes
1
answer
4k
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 ...
- 6,974
9
votes
2
answers
619
views
Justify text from a file using a LaTeX method
I wrote a bit of code that takes a file, justifies the text and writes to another file.
It uses a DP approach to minimise a badness metric, which is the amount of undershoot of the line length, cubed ...
- 2,393
9
votes
1
answer
2k
views
LeetCode on Longest Palindromic Substring in Python
This is a programming question from LeetCode:
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Note: "aba" is ...
user5235