OmarioVIC's blog

By OmarioVIC, history, 2 years ago, In English

what is the different of usage between Dp and memoization ?. I always use the memoization in problems then I see others' solutions , they use dp iterative. should I learn the dp and how can I be good at it

  • Vote: I like it
  • -15
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it
  • Dynamic programming is a technique that breaks a problem into smaller problems then merges the solutions in an efficient way.
  • Memoization is a technique that stores previously computed states for later use in order to avoid computing the same thing multiple times, so it can be used in dynamic programming. Think about memoization as a top-down approach: You start with the final state you want to compute then you recursively ask about the smaller states, stopping when you arrive at a state you already asked about.
  • Dynamic programming often uses a bottom-up approach: You start at the lower values / states then work your way up, finding the solution for each value one by one. This order let's you get rid of a recursive implementation and instead directly access the values you need, but you can also implement dp with the memoization approach.

A classic example of the difference between bottom-up and top-down is computing the nth element of the Fibonacci sequence. Bottom-Up:

int get_fib(int N) {
    vector<int> fib(N+1);
    fib[0] = 1;
    fib[1] = 1;
    for(int i = 2; i <= N; i ++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[N];
}

Top-Down:

int fib[mx];
int get_fib(int N) {
    if(fib[N]) { return fib[N]; }
    return fib[N] = get_fib(N-1) + get_fib(N-2);
}
// set fib[1] = 1 and set[2] = 1

I would recommend trying to solve some problems with a bottom-up approach, since it gives you a clear idea of the flow of the program and in my experience less is less prone to errors (it also sometimes speed things up). Good luck!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I would recommend copying this and saving it for later for other inevitable questions.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      That's a great example of an advantage in the top-down approach using memoization! You start with the current question then search for smaller already-answered questions that can help, instead of iterating through every possible question :D

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I wonder how to be efficient in Dp which is more than one-dimensional.

        I can think of logic but am not able to implement it.

        Any suggestions?