DISQUS

DISQUS Hello! 20bits is using DISQUS, a powerful comment system, to manage its comments. Learn more.

Community Page

Jump to original thread »
Author

Introduction to Dynamic Programming | 20bits

Started by Jesse Farmer · 7 months ago

No excerpt available. Jump to website »

30 comments

  • Nice. First time I've seen an interative algorthm development laid out, it just makes sense. Thanks for the post
  • Typo! Minus 4 points.

    "... plays a roll..."
  • Check your msum2 on [1,2,-4,1]
  • 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].
  • 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.
  • Oops, sorry, my bad. Somehow mis-interpreted the code (even knowing that this algorithm works) :(
  • > 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?
  • Hey Jesse,

    Great post. What wordpress plugin do you use to embed code in your posts?

    Thanks
  • CT,

    It's called Dean's Code Highlighter.
  • good work man...[:)]
    give some code implementation also...
  • 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
  • Nice explaination! Check out some more dynamic programming puzzles on fudge.
    http://fudge.fit.edu/Problems/Archive
  • Typo: overlappling
  • Really very nicely written. So easy was this to understand. Thank you.
  • 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.)
  • 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 .
  • 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]))

    Cheers
    Horst
  • What tool did you used to create this figures (http://20bits.com/include/images/fib_performanc...
  • re: Memoization

    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.
  • Jack,

    I'm using a Ruby graphing library called Gruff.
  • Horst,

    Thanks. I wrote this like a year and a half ago — I'm surprised nobody has caught that yet.
  • 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.
  • 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.
  • offo,

    Sorry for making you work so hard. Do you have any examples of good graphs?

    Help me learn — don't just berate me.
  • 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
  • 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
  • you should make a function that returns the nth fibonacci number without using recursion.
  • Excellent..
  • Superb tutorial..........nice one!!!!
  • Nice work. Keep it up.....

Add New Comment

Returning? Login