LeetCode刷题之动态规划的解题方法及相关练习(一)

迈不过友情╰ 2022-12-01 14:20 131阅读 0赞

注意： 切忌望文生义，用动态规划的名字反推算法！实际上，动态规划更像是高中数列题的升级版。

--------------------

#### 能用动态规划解决的问题需要满足的两点 ####

1.  大问题拆分成小问题
2.  小问题被重复调用

--------------------

#### 应用动态规划——将动态规划拆分成[三个子目标][Link 1] ####

**1. 建立状态转移方程:**

一个思维：当知 f(1)~f(n-1)的值，然后想办法利用它们求得f(n)

**2. 缓存并复用以往结果**

如果没有合适的处理，时间复杂度很有可能会是指数型的

**3. 按顺序从小往大算**

--------------------

#### 例子： ####

**一. 斐波那契数列（简单）**

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……  
它遵循这样的规律：当前值为前两个值的和。那么第n个值为多少？

首先，我们可以很容易得到状态转移方程： f ( n ) = f ( n − 1 ) + f ( n − 2 ) , n > = 2 f(n) = f(n-1) + f(n-2), n >= 2 f(n)=f(n−1)\+f(n−2),n>=2

**1. 简单递归(反例):**

def fib(n):
    	if n < 2:
    		return n
    	else:
    		return fib(n-1) + fib(n-2)
    		
    print(fib(100))

时间复杂度指数级别，和没有写效果一样  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]  
**2. 动态规划**

def fib(n):
        result = list(range(n+1)) # 缓存以往的结果，方便复用（目标2）
        
        for i in range(n+1):      # 按顺序从小往大算（目标3）
            if i < 2:
                result[i] = i
            else:
                # 使用状态转移方程（目标1），同时复用以往结果（目标2）
                result[i] = result[i-1] + result[i-2] 
        
        return result[-1]
    
    if __name__ == "__main__":
        result = fib(100)
        print(result)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

**二、不同路径（困难）**

[多味的LeetCode — 62. 不同路径][LeetCode _ 62.]

class Solution():
        def uniquePaths(self, m, n):   # 将二维列表初始化为1，以便之后用于缓存（目标2）
            dp = [[1]*n]*m
    
            for i in range(1, m):      # 外循环逐行计算（目标3）
                for j in range(1, n):  # 内循环逐行计算（目标3）
                    dp[i][j] = dp[i][j-1] + dp[i-1][j]  # 状态方程（目标1），以及中间结果复用（目标2）
    
            return dp[m-1][n-1]
    
    s = Solution()
    m = 3
    n = 2
    print(s.uniquePaths(m, n))

--------------------

### 升华篇： ###

[LeetCode刷题之动态规划的解题方法及相关练习(二)][LeetCode]

[Link 1]: https://www.zhihu.com/question/39948290
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/3442d7fd6eaa4946bee1fcc700024906.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/3a8a14f8300648aa8a22ad786998253e.png
[LeetCode _ 62.]: https://blog.csdn.net/weixin_43283397/article/details/104668226
[LeetCode]: https://blog.csdn.net/weixin_43283397/article/details/106978337