20bits: Introduction to Dynamic Programming | 20bits
Glenn
· 2 years ago
Nice. First time I've seen an interative algorthm development laid out, it just makes sense. Thanks for the post
Alex F
· 2 years ago
Typo! Minus 4 points.
"... plays a roll..."
EK
· 2 years ago
Check your msum2 on [1,2,-4,1]
Jesse
· 2 years ago
EK,
Looks good to mean. I get the maximum sum to be 3 and the range to be (0,2). The range it returns is meant to be applied in python, so that, e.g., (0,2) means [1,2,-4,1][0:2].
Aaron
· 2 years ago
haskell does not automatically memoize. It would be legal for a compiler to do so, but as it makes the time/space tradeoffs non-obvious no one does.
EK
· 2 years ago
Oops, sorry, my bad. Somehow mis-interpreted the code (even knowing that this algorithm works) :(
Mike
· 2 years ago
> If t + a[i] is negative, however, the contiguity constraint > means that we cannot include a[j:i+1] in our subarray since > any such subarray will have a smaller sum than a subarray without it.
What if all the numbers in the array are negative? I guess this is okay if the Maximum Subarray can be zero length.
If the subarray can't be zero length, do we have to go to a O(N^2) solution? Would it suffice to keep track of the largest single number?
CT
· 1 year ago
Hey Jesse,
Great post. What wordpress plugin do you use to embed code in your posts?
Thanks
Jesse
· 1 year ago
CT,
It's called Dean's Code Highlighter.
eatesh
· 1 year ago
good work man...[:)] give some code implementation also...
miriaim
· 1 year ago
please send me some characteristic of dynamic programming, multi stage decision process, max-min and min-max route all in dynamic programming to miriamudele4real@yahoo.co.uk
Really very nicely written. So easy was this to understand. Thank you.
John
· 1 year ago
thank you, i enjoyed your article, but i do think you could clarify part of the maximal sum section. i had the same problem as EK because it's not made explicit in the description that when you change j, you don't change the bounds or s. (it's clear from the code, though).
specifically the phrase "if t+a[i] is negative set t = 0 and set the left-hand bound of the optimal subarray to i+1" should be revised, since actually the optimal subarray does not change; only the starting point of further consideration changes. (consider [1,2,-5,1,1,-2]: t goes negative but the optimal subarray remains at the front.)
John Mount
· 1 year ago
Nice introduction to dynamic programming. Some of your readers might enjoy the small article on the doing arithmetic using dynamic programming and how you can use it to bet on the world series: http://www.win-vector.com/dfiles/BestOf.pdf .
Horst
· 1 year ago
Great article, I would like to read more of these!
But it seems I'm the first one to actually try your function A(..), as it doesn't work:
>>> A([10, 20], [30, 40], 2, 10000) Traceback (most recent call last): File "", line 1, in File "", line 3, in A IndexError: list index out of range
You're mixing zero-based arrays (Python) and one-based arrays (your text), so the correct function A would look like this:
def A(w, v, i,j): if i == 0 or j == 0: return 0 if w[i-1] > j: return A(w, v, i-1, j) else: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))
Perl also has a module called Memoize and its been part of the core Perl library for some years now.
Here's an article about Memoization by the author of the above module.
/I3az/
PS. Nice article.
Jesse
· 1 year ago
Jack,
I'm using a Ruby graphing library called Gruff.
Jesse
· 1 year ago
Horst,
Thanks. I wrote this like a year and a half ago — I'm surprised nobody has caught that yet.
Metta
· 1 year ago
Great post - simple introduction to a complex algorithmic concept.
Regarding the knapsack problem, once the table is ready, the complexity is indeed only O(nW) But building the table itself is of exponential cost in terms of running time, correct? We go through every single possibility using recursion to build the table, and I think running time to build the table is n^m. It would be great if you could clarify.
offo foffo
· 11 months ago
Ok if I want to a view an image I don't want to see some stupid transition. Show me the goddamn image.
Second, your graphs are hard to read. Why does your graph use a gradient background? The change in contrast makes it difficult to read and gives really no benefit.
Also your graphs go against the norm, the label of the y axis is upside down. I don't care if it is your software or some designer jerk being a douchebag suggesting this is better...
IT ISN'T. I have to parse through 100s of chart a day in my day job and this kind of shit just pisses me off. I shouldn't have to fight with your eye-candy.
Jesse
· 11 months ago
offo,
Sorry for making you work so hard. Do you have any examples of good graphs?
Help me learn — don't just berate me.
SimonTewbi
· 11 months ago
Great article, thanks Jesse.
By the way, I believe your fib2 function is missing a line. It is incorrect for n=0. I think it should read:
def fib2(n): if n == 0: return 0 n2, n1 = 0, 1 for i in range(n-2): n2, n1 = n1, n1 + n2 return n2 + n1
Cheers Simon
SimonTewbi
· 11 months ago
Come to think of it, I think this might be cleaner:
def fib2(n): n2, n1 = 0, 1 for i in range(n): n2, n1 = n1, n1 + n2 return n2
james
· 11 months ago
you should make a function that returns the nth fibonacci number without using recursion.
All Comments
"... plays a roll..."
Looks good to mean. I get the maximum sum to be 3 and the range to be (0,2). The range it returns is meant to be applied in python, so that, e.g., (0,2) means [1,2,-4,1][0:2].
> means that we cannot include a[j:i+1] in our subarray since
> any such subarray will have a smaller sum than a subarray without it.
What if all the numbers in the array are negative? I guess this is okay if the Maximum Subarray can be zero length.
If the subarray can't be zero length, do we have to go to a O(N^2) solution? Would it suffice to keep track of the largest single number?
Great post. What wordpress plugin do you use to embed code in your posts?
Thanks
It's called Dean's Code Highlighter.
give some code implementation also...
http://fudge.fit.edu/Problems/Archive
specifically the phrase "if t+a[i] is negative set t = 0 and set the left-hand bound of the optimal subarray to i+1" should be revised, since actually the optimal subarray does not change; only the starting point of further consideration changes. (consider [1,2,-5,1,1,-2]: t goes negative but the optimal subarray remains at the front.)
But it seems I'm the first one to actually try your function A(..), as it doesn't work:
>>> A([10, 20], [30, 40], 2, 10000)
Traceback (most recent call last):
File "", line 1, in
File "", line 3, in A
IndexError: list index out of range
You're mixing zero-based arrays (Python) and one-based arrays (your text), so the correct function A would look like this:
def A(w, v, i,j):
if i == 0 or j == 0: return 0
if w[i-1] > j: return A(w, v, i-1, j)
else: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))
Cheers
Horst
Perl also has a module called Memoize and its been part of the core Perl library for some years now.
Here's an article about Memoization by the author of the above module.
/I3az/
PS. Nice article.
I'm using a Ruby graphing library called Gruff.
Thanks. I wrote this like a year and a half ago — I'm surprised nobody has caught that yet.
Regarding the knapsack problem, once the table is ready, the complexity is indeed only O(nW)
But building the table itself is of exponential cost in terms of running time, correct?
We go through every single possibility using recursion to build the table, and I think running time to build the table is n^m. It would be great if you could clarify.
Second, your graphs are hard to read. Why does your graph use a gradient background? The change in contrast makes it difficult to read and gives really no benefit.
Also your graphs go against the norm, the label of the y axis is upside down. I don't care if it is your software or some designer jerk being a douchebag suggesting this is better...
IT ISN'T. I have to parse through 100s of chart a day in my day job and this kind of shit just pisses me off. I shouldn't have to fight with your eye-candy.
Sorry for making you work so hard. Do you have any examples of good graphs?
Help me learn — don't just berate me.
By the way, I believe your fib2 function is missing a line. It is incorrect for n=0. I think it should read:
def fib2(n):
if n == 0: return 0
n2, n1 = 0, 1
for i in range(n-2):
n2, n1 = n1, n1 + n2
return n2 + n1
Cheers
Simon
def fib2(n):
n2, n1 = 0, 1
for i in range(n):
n2, n1 = n1, n1 + n2
return n2