1. Start with a frog
If a frog wants to jump down n steps into the pool, it can jump 1 or 2 steps at a time. How many ways does it have to jump down the pool (e.g., n=30)?
In the language of mathematics, we need to ask a frog jump function f(n). For such a function whose independent variable is a non-negative integer, we can start from a relatively small case, it is not difficult to get f(1)=1, f(2)=2, the problem is that later enumerations become more and more troublesome.
Imagine that you are the frog, facing n steps, and the first time you can jump one step, that leaves n-1, f(n-1), and the first time you can jump two steps, that leaves n-2, f(n-2), so the answer to this question is familiar, and it’s the magic Fibonacci sequence:
? \begin{aligned} F_{0} &=0 \ F_{1} &=1 \ F_{n} &=F_{n-1}+F_{n-2} \quad(\mathrm{n} \geq 2) \end{aligned} ?
The first step in solving this kind of function evaluation problem is to find a recurrence. We translate the recursion into Python code:
def fib(n) :
if n==0:
return 1
if n==1:
return 1
return fib(n-1)+fib(n-2)
Copy the code%%time
fib(30)
Wall time: 269 ms
832040
Copy the codeRunning time 284ms, slow enough, why slow? Because there are too many repeated calculations, taking f(5) as an example, the call relationship is as follows:
f(5)==>f(4), f(3)
f(4)==>f(3), f(2), f(3)==>f(2), f(1)
f(3)==>f(2), f(1), f(2)==>f(1), f(0), f(2)==>f(1), f(0), f(1)
f(2)==>f(1), f(0), f(1), f(1), f(0), f(1), f(0), f(1)
f(1), f(0), f(1), f(1), f(0), f(1), f(0), f(1)
Copy the codeSo the natural idea would be to cache all the intermediate results, and fortunately, Python has this “battery” built in.
from functools import lru_cache
@lru_cache()
def fib(n) :
if n==0:
return 1
if n==1:
return 1
return fib(n-1)+fib(n-2)
Copy the code%%time
fib(30)
Wall time: 0 ns
832040
Copy the codeIt was too soon to measure the time. The basic principle of Lru_cache in Python is to build a dictionary whose key is the call parameter and value is the result of that parameter’s calculation. Roughly equivalent to the following code:
def fib(n) :
if n in fib.cache:
return fib.cache[n]
if n==0:
ans = 1
elif n==1:
ans = 1
elif:
ans = fib(n-1)+fib(n-2)
fib.cache[n] = ans
return ans
fib.cache = {}
Copy the codeOf course, for this problem, we can use a more detailed caching method, or even replace the recursion with a loop (equivalent to only keeping two caches, which greatly reduces the space occupied, but if we need to repeatedly calculate each n value, then maybe the former method is more appropriate) :
def fib(n) :
a, b = 0.1
for i in range(n):
a, b = b, a+b
return a
Copy the codePython3 = leetcode 70 python3 = leetcode 70
from functools import lru_cache
class Solution:
@lru_cache()
def climbStairs(self, n: int) - >int:
if n==0:
return 1
if n==1:
return 1
return self.climbStairs(n-1)+self.climbStairs(n-2)
Copy the codeThe execution time was 52 ms and the memory consumption was 13.2MB.
2. Simplified practical version of dynamic programming
We take a more general lesson from the frog to solve a similar problem of constructable recursive functions:
- To find a recursive relation and establish a recursive function, the problem becomes the solution of multiple sub-problems.
- To prevent computations of the same subproblem over and over again, use caching and trade space for time.
In general algorithm textbooks or interview problem solving, will spend a lot of time to design this cache structure, in practical engineering problems, we may not be so sensitive to the use of more cache space, so only need to develop recursive functions, coupled with a general cache scheme will basically solve the problem. It is only when cache space becomes an issue that we need to consider further smaller caches to accommodate the problem.
To check this out, let’s look at a few more problems, and just swipe a few more in Leetcode.
Maximum suborder sum
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
Example:
Input: [– 2, 1, 3, 4, 1, 2, 1, 5, 4], output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.
Let’s consider the recurrence of the maximum sum that we can get at the end of each position in the array. ? \begin{aligned} f(0)&=nums(0) \ f(k)&=max(f(k-1), 0)+nums(k) \quad(k>0) \end{aligned} ? Based on this, it is not difficult to get the final result as? ans = max_{i=0}^n(f(i)) ? The code translated to PYTHon3 in Leetcode is as follows:
from functools import lru_cache
class Solution:
def maxSubArray(self, nums: List[int]) - >int:
self.nums = nums
return max(self.f(i) for i in range(len(nums)))
@lru_cache()
def f(self, k) :
if k == 0:
return self.nums[0]
else:
return max(self.f(k-1), 0) + self.nums[k]
Copy the codeThe execution time is 76 ms, and the memory consumption is 13.7 MB.
Minimum path sum
Given an M x N grid of non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path.
Example:
,3,1 input: [[1],,5,1 [1], [4, 2, 1]] output: 7 explanation: because the path 1-3-1-1-1 the sum of the minimum.
Take each position in the matrix as the lower right corner, find the minimum path sum, and it is not difficult to get the following recursive formula:? \begin{aligned} f(0, 0)&=grid(0, 0) \ f(x, 0)&=f(x-1, 0)++grid(x, 0) \quad(x>0) \ f(0, y)&=f(0, y-1)++grid(0, y) \quad(y>0) \ f(x, y)&=min(f(x-1, y), f(x, y-1))+grid(x, y) \quad(x>0, y>0) \end{aligned} ?
The code translated to PYTHon3 in Leetcode is as follows:
from functools import lru_cache
class Solution:
def minPathSum(self, grid: List[List[int]]) - >int:
self.grid = grid
return self.f(len(grid)-1.len(grid[0]) -1)
@lru_cache()
def f(self, x, y) :
if x == 0 and y == 0:
return self.grid[0] [0]
elif y == 0:
return self.f(x-1.0) + self.grid[x][0]
elif x == 0:
return self.f(0, y-1) + self.grid[0][y]
else:
return min(self.f(x-1,y), self.f(x,y-1)) + self.grid[x][y]
Copy the codeThe execution time is 1052ms, and the memory consumption is 13.9M.