Блог пользователя OmarioVIC

Автор OmarioVIC, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
  • 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!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      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