Common DP techniques - Go教程

- [Instructor] Now that you understand the importance, benefits, and typical use cases of dynamic programming, or DP, we can learn some of its common techniques. The first programming technique that's used together with DP is recursion. A recursive function invokes itself during execution. Often recursive functions invoke themselves with different parameters which represent subproblems they're trying to solve. Function invocations are added to the call stack in the order in which they are called. The call runtime will respect this order during execution. A very important aspect of recursion is the end condition. Every recursive function must have an execution path or condition where the function stops invoking itself. If this condition is not included or never reached, the recursive function will continue calling itself until it exhausts CPU resources. A common problem used to illustrate and introduce the concept of recursive algorithms is by using the Fibonacci series. You've probably seen this example before. The Fibonacci sequence is a series of numbers where each number is made up of the sum of the preceding two numbers. The series begins with zero and one. The diagram presented here demonstrates the function calls required for calculating a series of five Fibonacci numbers. The recursive fib function is easy to implement based on the subproblem breakdown that we've already established. The function has two end conditions for zero and one, which we declare at the top of the function. After the end conditions, the function invokes itself with the proceeding two numbers as parameters. The recursive function we've written so far will work to compute Fibonacci numbers, but it does quite a bit of repeated work. Looking at the recursive calls required for calculating the fifth Fibonacci number, there are quite a few numbers that are calculated multiple times. This effect will only be amplified for larger numbers until eventually we will not be able to use it for calculation regardless of how much computing power we have. In order to reduce these repeated computations, practitioners of DP use a technique called memorization. This involves building a cache or data structure to save the results of subproblems in order to avoid expensive duplicated recalculations. Memorization can help in optimizing the work and resources required by our recursive fib function. We can create a computed fib map, which saves indices alongside their computed values. In the fib function, begin by checking whether the computed fib map contains the value already. If it does, then we simply return it without any further computations. If the value is not found in the cache, then compute it using recursion, save it to the computed fib map for future reuse, and then return. It's important to consider what duplicated computations DP algorithms will have to undergo because effects compound with larger numbers or inputs. Memorization is easy to add to recursive algorithms, so make sure you consider adding it to your solutions.