# 从暴力递归到动态规划

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-17%2001%3A31%3A10\&color=yellowgreen\&style=flat-square)

* [概述](#概述)
* [经典问题](#经典问题)
  * [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)
```

<details>

<summary><strong>记忆化搜索 (不使用标准库)</strong></summary>

```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)
```

</details>

<details>

<summary><strong>迭代写法 (无滚动优化)</strong></summary>

```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]
```

</details>

#### 示例 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)
```

<details>

<summary><strong>迭代写法</strong></summary>

```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]
```

</details>

#### 示例 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:]]
```

<details>

<summary><strong>迭代写法</strong></summary>

```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:]]
```

</details>

### 2. 多样本位置全对应的尝试模型

### 3. 范围内的尝试模型

### 4. 寻找业务限制的尝试模型

> 该类型原文只给了很难的几个例子, 感兴趣的可以去看原视频;

## 更多相关问题

> algorithms/[暴力递归与动态规划](https://imhuay.gitbook.io/studies/algorithms#暴力递归与动态规划)

## 参考资料

* [暴力递归到动态规划 - 左程云算法教程 (p52)](https://www.bilibili.com/video/BV1NU4y1M7rF?p=52)