Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

7
  • 9
    $\begingroup$ That's memoization, which is just one of many tricks that DP employs. $\endgroup$ Commented Apr 9, 2014 at 18:15
  • 4
    $\begingroup$ Brute force with memoisation is still inefficient; only additional structure/pruning provided by DP recurrences make memoisation pay off. $\endgroup$ Commented Apr 9, 2014 at 22:37
  • 3
    $\begingroup$ I don't know anything about dynamic programming, but I'm fairly sure there's more to it than just adding caches to a brute-force algorithm. I think dynamic programming avoids testing every possible combination by subdividing the problem space, finding an optimal solution for each small subdivision, and then combining them to create an overall best solution. (It might do this recursively, sub-diving the sub-divisions.) This only works if you can express the problem in a way that allows for combination of solutions like this and still get an overall optimum. $\endgroup$ Commented Apr 10, 2014 at 8:06
  • 1
    $\begingroup$ This answer is actually quite accurate. I advise reading a textbook like Cormen et al: "Introduction to Algorithms" to learn more about dynamic programming, this book has a quite decent chapter on it. In a nutshell, efficient dynamic programming makes use of two properties of the (optimization) problem you want to solve: optimal solutions can be constructed from the optimal solutions of smaller sub-problems, and the total number of smaller sub-problems is actually rather small. Then, you can build all sub-problem solutions bottom-up, accelerating the computation at the cost of memory. $\endgroup$ Commented Apr 10, 2014 at 12:14
  • $\begingroup$ Or, to put it in even simpler terms: If you know how to compute a binomial coefficient using Pascal's triangle then you know all you ever need to know about dynamic programming. $\endgroup$ Commented Apr 10, 2014 at 12:28