DISQUS

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

Community Page

20bits

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

  • Glenn

    2 years ago

    Nice. First time I've seen an interative algorthm development laid out, it just makes sense. Thanks for the post
    reply
  • Alex F

    2 years ago

    Typo! Minus 4 points.

    "... plays a roll..."
    reply
  • EK

    2 years ago

    Check your msum2 on [1,2,-4,1]
    reply
  • 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].
    reply
  • 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.
    reply
  • EK

    2 years ago

    Oops, sorry, my bad. Somehow mis-interpreted the code (even knowing that this algorithm works) :(
    reply
  • 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?
    reply
  • CT

    1 year ago

    Hey Jesse,

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

    Thanks
    reply
  • Jesse

    1 year ago

    CT,

    It's called Dean's Code Highlighter.
    reply
  • eatesh

    1 year ago

    good work man...[:)]
    give some code implementation also...
    reply
  • 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
    reply
  • David

    1 year ago

    Nice explaination! Check out some more dynamic programming puzzles on fudge.
    http://fudge.fit.edu/Problems/Archive
    reply
  • Trevor

    1 year ago

    Typo: overlappling
    reply
  • Pratyush

    1 year ago

    Really very nicely written. So easy was this to understand. Thank you.
    reply
  • John

    9 months 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.)
    reply
  • John Mount

    9 months 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 .
    reply
  • Horst

    9 months 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]))

    Cheers
    Horst
    reply
  • Jack

    9 months ago

    What tool did you used to create this figures (http://20bits.com/include/images/fib_performanc...
    reply
  • draegtun

    9 months ago

    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.
    reply
  • Jesse

    9 months ago

    Jack,

    I'm using a Ruby graphing library called Gruff.
    reply
  • Jesse

    9 months ago

    Horst,

    Thanks. I wrote this like a year and a half ago — I'm surprised nobody has caught that yet.
    reply
  • Metta

    8 months 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.
    reply
  • offo foffo

    7 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.
    reply
  • Jesse

    7 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.
    reply
  • SimonTewbi

    7 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
    reply
  • SimonTewbi

    7 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
    reply
  • james

    7 months ago

    you should make a function that returns the nth fibonacci number without using recursion.
    reply
  • Nilavalagan

    1 month ago

    Excellent..
    reply
  • biker

    2 weeks ago

    Superb tutorial..........nice one!!!!
    reply
  • pickatutorial

    2 weeks ago

    Nice work. Keep it up.....
    reply

Add New Comment

Returning? Login