We know that if we don’t do any processing, we will repeat too many calculations, which is very bad The processing idea will avoid repeated calculation
Python Code
1 2 3 4 5
classSolution2: @functools.lru_cache() deffib(self, N: int) -> int: if N <= 1: return N else:returnself.fib(N - 1) + self.fib(N - 2)
Recursion, iteration, divide and conquer, backtracking, they do not have a clear distinction Recursion:The core idea is to govern separately and unify the officials
1 2 3 4 5 6 7
class Solution: def fib(self, N:int) -> int: memo = {} ifN < 2: return N ifN-1not in memo: memo[N-1] = self.fib(N-1) ifN-2not in memo: memo[N-2] = self.fib(N-2) return memo[N-1] + memo[N-2]
Dynamic recursion(Bottom up)
Basic solutions
More initial value, continuous dynamic recursive
Python Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
class Solution: def fib(self, N: int) -> int: ifN < 2: returnN dp = [0for _ in range(N + 1)] dp[0], dp[1] = 0, 1 for i in range(2, N + 1): dp[i] = dp[i - 1] + dp[i - 2] returndp[- 1]
class Solution: def fib(self, N: int) -> int: ifN == 0: return0 memo = [0,1] for _ in range(2,N+1): memo = [memo[-1], memo[-1] + memo[-2]] return memo[-1]
Java Code
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { publicint fib(int N) { if (N <= 1) return N; if (N == 2) return1; int curr = 0, prev1 = 1, prev2 = 1; for (int i = 3; i <= N; i++) { curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return curr; } }
Use better base types (tuples) to improve performance