Last updated
以斐波那契数列为例:
f(5)
f(4) f(3)
f(3) f(2) ...class Solution:
def climbStairs(self, n: int) -> int:
from functools import lru_cache
@lru_cache
def dfs(i): # 爬 i 阶存在的方法数
if i <= 1: return 1
# 爬 i 阶的方法数 = 爬 i - 1 阶的方法数 + 爬 i - 2 阶的方法数
return dfs(i - 1) + dfs(i - 2)
return dfs(n)class Solution:
def climbStairs(self, n: int) -> int:
cache = dict() # 缓存
def dfs(i):
if i in cache: return cache[i] # 搜索"记忆"
if i <= 1: ret = 1
else: ret = dfs(i - 1) + dfs(i - 2)
cache[i] = ret # "记忆"
return ret
return dfs(n)class Solution:
def climbStairs(self, n: int) -> int:
dp = [0] * (n + 1)
for i in range(n + 1):
if i <= 1: dp[i] = 1 # if i <= 1: return 1
else: dp[i] = dp[i - 1] + dp[i - 2] # dfs(i - 1) + dfs(i - 2)
return dp[-1]class Solution:
def numDecodings(self, s: str) -> int:
from functools import lru_cache
@lru_cache
def dfs(i): # s[0: i+1] 的解码方法数
# 最容易出错的点, 以 0 开头的字符串不存在相应的编码
if i <= 0: return int(s[0] != '0')
ret = 0
if '1' <= s[i] <= '9': # 如果 s[i] 在 0~9, 存在相应的编码
ret += dfs(i - 1) # s[i-1] == 1 和 s[i-2] 的特殊讨论
if s[i - 1] == '1' or s[i - 1] == '2' and '0' <= s[i] <= '6':
ret += dfs(i - 2)
return ret
return dfs(len(s) - 1)class Solution:
def numDecodings(self, s: str) -> int:
# if s[0] == '0': return 0
dp = [0] * (len(s) + 1)
# dp[-1] = dp[0] = int(s[0] != '0')
# 注意 i 的范围与递归中一致, 这里利用了 python 中 list[-1] 特性, 避免了下标的调整
for i in range(-1, len(s)):
# 下面就是把递归中的代码搬过来
if i <= 0: # 如果把这一段拿到循环外, 需要调整 i 的遍历范围
dp[i] = int(s[0] != '0')
continue
dp[i] = 0
if '1' <= s[i] <= '9':
dp[i] += dp[i - 1]
if s[i - 1] == '1' or s[i - 1] == '2' and '0' <= s[i] <= '6':
dp[i] += dp[i - 2]
return dp[len(s) - 1]class Solution:
def dicesProbability(self, n: int) -> List[float]:
def dfs(k):
if k == 1:
return [1] * 7
dp_pre = dfs(k - 1)
dp = [0] * (k * 6 + 1)
for i in range(1 * (n - 1), 6 * (n - 1) + 1): # n - 1 个骰子的点数范围
for d in range(1, 7): # 当前骰子掷出的点数 (跳的台阶数)
dp[i + d] += dp_pre[i]
return dp
dp = dfs(n)
return [x / (6 ** n) for x in dp[n:]]class Solution:
def dicesProbability(self, n: int) -> List[float]:
dp = [1] * 7
for k in range(2, n + 1):
dp_pre = dp
dp = [0] * (k * 6 + 1)
for i in range(1 * k, 6 * k + 1): # n 个骰子的点数范围
for d in range(1, 7): # 当前骰子掷出的点数
if 1 * (k - 1) <= i - d <= 6 * (k - 1):
dp[i] += dp_pre[i - d]
return [x / (6 ** n) for x in dp[n:]]