# 从暴力递归到动态规划
* [概述](#概述)
* [经典问题](#经典问题)
* [1. 自底向上的递归/迭代](#1-自底向上的递归迭代)
* [示例 1: 跳台阶 (一维)](#示例-1-跳台阶-一维)
* [示例 2: 解码方法 (一维, "跳台阶" 变体)](#示例-2-解码方法-一维-跳台阶-变体)
* [示例 3: N 个骰子的点数 (一维, "跳台阶" 变体)](#示例-3-n-个骰子的点数-一维-跳台阶-变体)
* [2. 多样本位置全对应的尝试模型](#2-多样本位置全对应的尝试模型)
* [3. 范围内的尝试模型](#3-范围内的尝试模型)
* [4. 寻找业务限制的尝试模型](#4-寻找业务限制的尝试模型)
* [更多相关问题](#更多相关问题)
* [参考资料](#参考资料)
## 概述
* 从代码角度, 动态规划的实现一般都是通过迭代完成的 (递推公式); 而一般迭代过程都有与之对应的递归写法;
> 这里默认动态规划都是基于迭代的实现. 实际上, 动态规划只是一种算法, 跟具体实现无关, 递归实现也是动态规划;
* 递归过程一般与人的直接思考过程更接近, 因此如果对递归结构比较熟悉, 就能更容易的写出相应解法;
> 动态规划的难点是递推过程 (经验和数学能力); 递归的难点是递归结构本身;
* 递归的一个问题是如果存在重复计算, 会大幅降低性能, 此时有两个解决方法:
1. 转换为迭代结构; 转化过程可以套用固定模板, 详见示例;
2. 使用记忆化搜索, 即保存中间结果; 如果用 python 书写, 可以使用 `functools.lru_cache` 装饰器, 详见示例;
3. 如何判断是否存在重复计算?
> 将递归过程展开为树状结构，当发现某些具有相同参数的递归调用出现在多个不同节点时，说明存在重复调用；
```
以斐波那契数列为例:
f(5)
f(4) f(3)
f(3) f(2) ...
```
4. 什么情况下可以使用**记忆化搜索**?
> 这个问题的本质, 实际上是判断问题本身是不是一个动态规划问题; 能用动态规划解决的问题必须具备**无后效性**, 只要具备这个特性, 就可以使用记忆化搜索;
>
> > 无后效性: 某阶段的状态一旦确定, 则此后过程的决策不再受此前各种状态及决策的影响.
## 经典问题
* 原文总结了 4 种常见的递归过程，基本能覆盖大部分场景；
### 1. 自底向上的递归/迭代
* 最常见的递归模型, 一般过程:
1. 确定初始状态 (递归基), 即 $k=0$ 时刻的状态）
2. 假设已知 $k-1$ 及其之前时刻的状态，推导 $k$ 时刻的状态；
> 有时候可能是自顶向下, 本质是一样的;
#### 示例 1: 跳台阶 (一维)
> [70. 爬楼梯 - 力扣（LeetCode）](https://leetcode.cn/problems/climbing-stairs/)
* 该模型下的一维问题几乎都是 "**跳台阶**" 问题的变体;
```python
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)
```
记忆化搜索 (不使用标准库)
```python
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)
```
迭代写法 (无滚动优化)
```python
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]
```
#### 示例 2: 解码方法 (一维, "跳台阶" 变体)
> [91. 解码方法 - 力扣（LeetCode）](https://leetcode.cn/problems/decode-ways/)
* 有限制的 "跳台阶" 问题;
```python
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)
```
迭代写法
```python
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]
```
#### 示例 3: N 个骰子的点数 (一维, "跳台阶" 变体)
> [剑指 Offer 60. n个骰子的点数 - 力扣（LeetCode）](https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/)
* 进阶版 "跳台阶", 相当于每次能跳的步数更多;
```python
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:]]
```
迭代写法
```python
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:]]
```
### 2. 多样本位置全对应的尝试模型
### 3. 范围内的尝试模型
### 4. 寻找业务限制的尝试模型
> 该类型原文只给了很难的几个例子, 感兴趣的可以去看原视频;
## 更多相关问题
> algorithms/[暴力递归与动态规划](https://imhuay.gitbook.io/studies/notes/_archives/2022/10/pages/R5NyOzkn3qAZy7wCx1pS#暴力递归与动态规划)
## 参考资料
* [暴力递归到动态规划 - 左程云算法教程 (p52)](https://www.bilibili.com/video/BV1NU4y1M7rF?p=52)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://imhuay.gitbook.io/studies/notes/_archives/2022/10/cong-bao-li-di-gui-dao-dong-tai-gui-hua.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.