What is the difference between memoization and dynamic programming?_问答_开发者

What is the difference between m开发者_JAVA技巧emoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?

Relevant article on Programming.Guide: Dynamic programming vs memoization vs tabulation

What is difference between memoization and dynamic programming?

Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.

Dynamic programming is a technique for solving problems of recursive nature, iteratively and is applicable when the computations of the subproblems overlap.

Dynamic programming is typically implemented using tabulation, but can also be implemented using memoization. So as you can see, neither one is a "subset" of the other.

A reasonable follow-up question is: What is the difference between tabulation (the typical dynamic programming technique) and memoization?

When you solve a dynamic programming problem using tabulation you solve the problem "bottom up", i.e., by solving all related sub-problems first, typically by filling up an n-dimensional table. Based on the results in the table, the solution to the "top" / original problem is then computed.

If you use memoization to solve the problem you do it by maintaining a map of already solved sub problems. You do it "top down" in the sense that you solve the "top" problem first (which typically recurses down to solve the sub-problems).

A good slide from ~~here~~ (link is now dead, slide is still good though):

If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor

No overhead for recursion and less overhead for maintaining table

There are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce the time or space requirements even further

If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required

Additional resources:

Wikipedia: Memoization, Dynamic Programming
Related SO Q/A: Memoization or Tabulation approach for Dynamic programming

Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.

http://www.geeksforgeeks.org/dynamic-programming-set-1/

Memoization is an easy method to track previously solved solutions (often implemented as a hash key value pair, as opposed to tabulation which is often based on arrays) so that they aren't recalculated when they are encountered again. It can be used in both bottom up or top down methods.

See this discussion on memoization vs tabulation.

So Dynamic programming is a method to solve certain classes of problems by solving recurrence relations/recursion and storing previously found solutions via either tabulation or memoization. Memoization is a method to keep track of solutions to previously solved problems and can be used with any function that has unique deterministic solutions for a given set of inputs.

Both Memoization and Dynamic Programming solves individual subproblem only once.

Memoization uses recursion and works top-down, whereas Dynamic programming moves in opposite direction solving the problem bottom-up.

Below is an interesting analogy -

Top-down - First you say I will take over the world. How will you do that? You say I will take over Asia first. How will you do that? I will take over India first. I will become the Chief Minister of Delhi, etc. etc.

Bottom-up - You say I will become the CM of Delhi. Then will take over India, then all other countries in Asia and finally I will take over the world.

Dynamic Programming is often called Memoization!

Memoization is the top-down technique(start solving the given problem by breaking it down) and dynamic programming is a bottom-up technique(start solving from the trivial sub-problem, up towards the given problem)
DP finds the solution by starting from the base case(s) and works its way upwards. DP solves all the sub-problems, because it does it bottom-up

Unlike Memoization, which solves only the needed sub-problems
DP has the potential to transform exponential-time brute-force solutions into polynomial-time algorithms.
DP may be much more efficient because its iterative

On the contrary, Memoization must pay for the (often significant) overhead due to recursion.

To be more simple, Memoization uses the top-down approach to solve the problem i.e. it begin with core(main) problem then breaks it into sub-problems and solve these sub-problems similarly. In this approach same sub-problem can occur multiple times and consume more CPU cycle, hence increase the time complexity. Whereas in Dynamic programming same sub-problem will not be solved multiple times but the prior result will be used to optimize the solution.

(1) Memoization and DP, conceptually, is really the same thing. Because: consider the definition of DP: "overlapping subproblems" "and optimal substructure". Memoization fully possesses these 2.

(2) Memoization is DP with the risk of stack overflow is the recursion is deep. DP bottom up does not have this risk.

(3) Memoization needs a hash table. So additional space, and some lookup time.

So to answer the question:

-Conceptually, (1) means they are the same thing.

-Taking (2) into account, if you really want, memoization is a subset of DP, in a sense that a problem solvable by memoization will be solvable by DP, but a problem solvable by DP might not be solvable by memoization (because it might stack overflow).

-Taking (3) into account, they have minor differences in performance.

From wikipedia:

Memoization

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.

Dynamic Programming

In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems.

When breaking a problem into smaller/simpler subproblems, we often encounter the same subproblem more then once - so we use Memoization to save results of previous calculations so we don't need to repeat them.

Dynamic programming often encounters situations where it makes sense to use memoization but You can use either technique without necessarily using the other.

I would like to go with an example;

Problem:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

What is the difference between memoization and dynamic programming?

Recursion with Memoization

In this way we are pruning (a removal of excess material from a tree or shrub) recursion tree with the help of memo array and reducing the size of recursion tree upto nn.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Dynamic Programming

As we can see this problem can be broken into subproblems, and it contains the optimal substructure property i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems, we can use dynamic programming to solve this problem.

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Examples take from https://leetcode.com/problems/climbing-stairs/

Just think of two ways,

We break down the bigger problem into smaller sub problems - Top down approach.
We start from smallest sub problem and reach the bigger problem - Bottom up approach.

In Memoization we go with (1.) where we save each function call in a cache and call back from there. Its a bit expensive as it involves recursive calls.

In Dynamic Programming we go with (2.) where we maintain a table, bottom up by solving subproblems using the data saved in the table, commonly referred as the dp-table.

Note:

Both are applicable to problems with Overlapping sub-problems.
Memoization performs comparatively poor to DP due to the overheads involved during recursive function calls.
The asymptotic time-complexity remains the same.

There're some similarities between dynamic programming (DP) and memoization and in most cases you can implement a dynamic programming process by memoization and vise versa. But they do have some differences and you should check them out when deciding which approach to use:

Memoization is a top-down approach during which you decompose a big problem into smaller-size subproblems with the same properties and when the size is small enough you can easily solve it by bruteforcing. Dynamic Programming is a bottom-up approach during which you firstly calculate the answer of small cases and then use them to construct the answer of big cases.
During coding, usually memoization is implemented by recursion while dynamic programming does calculation by iteration. So if you have carefully calculate the space and time complexity of your algorithm, using dynamic-programming-style implementation can offer you better performance.
There do exist situations where using memoization has advantages. Dynamic programming needs to calculate every subproblem because it doesn't know which one will be useful in the future. But memoization only calculate the subproblems related to the original problem. Sometimes you may design a DP algorithm with theoretically tremendous amount of dp status. But by careful analyses you find that only an acceptable amount of them will be used. In this situation it's preferred to use memoization to avoid huge execution time.

In Dynamic Programming ,

No overhead for recursion, less overhead for maintaining the table.
The regular pattern of the table accesses may be used to reduce time or space requirements.

In Memorization,

Some subproblems do not need to be solved.

Here is a sample of Memoization and DP from Fibonacci Number problem written in Java.

Dynamic Programming here is not involving the recursion, as result faster and can calculate higher values because it is not limited by the execution stack.

public class Solution {

 public static long fibonacciMemoization(int i) {
    return fibonacciMemoization(i, new long[i + 1]);
 }

 public static long fibonacciMemoization(int i, long[] memo) {
    if (i <= 1) {
        return 1;
    }
    if (memo[i] != 0) {
        return memo[i];
    }
    long val = fibonacciMemoization(i - 1, memo) + fibonacciMemoization(i - 2, memo);
    memo[i] = val;
    return val;
 }

 public static long fibonacciDynamicPrograming(int i) {
    if (i <= 1) {
        return i;
    }
    long[] memo = new long[i + 1];
    memo[0] = 1;
    memo[1] = 1;
    memo[2] = 2;
    for (int j = 3; j <= i; j++) {
        memo[j] = memo[j - 1] + memo[j - 2];
    }
    return memo[i];
 }

 public static void main(String[] args) {
    System.out.println("Fibonacci with Dynamic Programing");
    System.out.println(fibonacciDynamicPrograming(10));
    System.out.println(fibonacciDynamicPrograming(1_000_000));

    System.out.println("Fibonacci with Memoization");
    System.out.println(fibonacciMemoization(10));
    System.out.println(fibonacciMemoization(1_000_000)); //stackoverflow exception
 }
}

Dynamic Programming is an optimization over plain recursive algorithm which consider all the combination of the input to provide the most suitable answer. This approach has one drawback, its huge time complexity. It can be made more efficient by the use of memoization. It will store every output of a subproblem and will directly give an answer, whenever that algorithm tries to solve that subproblem again. This can make the algorithm have polynomial time complexity.