三个月算法进阶--day21
目录
递归优化
记录已经算过的
lru_cache、函数外字典、函数内字典、装饰器内数组
动态规划
小问题组合为大问题，由底向上，推荐
数学法
寻找公式直接计算
尾递归
层数太深仍需优化
记录
leetcode第62题不同路径
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)
from functools import lru_cache
class Solution:
@lru_cache(maxsize=512)
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)
class Solution:
tmp = {}
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
if (m, n) in self.tmp:
return self.tmp[(m, n)]
self.tmp[(m, n)] = self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)
return self.tmp[(m, n)]
class Solution:
def uniquePaths(self, m: int, n: int, cache=None) -> int:
if cache is None: # don't use `not`
cache = {}
if (m, n) in cache:
return cache[(m, n)]
if m == 1 or n == 1:
return 1
cache[(m, n)] = self.uniquePaths(m-1, n, cache) + self.uniquePaths(m, n-1, cache)
return cache[(m, n)]
class Solution:
def memo(func):
cache = {}
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap
@memo
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)