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

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

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
  • Проголосовать: не нравится

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