【数据结构】动态规划（Dynamic programming，DP）

B站讲解
 知乎好文
适用题目特点

计数

有多少种方式走到右下角
有多少种方法选出 k 个数使得和是 Sum

求最大最小值

从左上角走到右下角路径的最大数字和
最长上升子序列长度

求存在性

取石子游戏，先手是否必胜
能不能选出 k 个数使得和是 Sum

最值型解题步骤

确定状态

最后一步（最优策略中使用的最后一枚硬币 ak）
化成子问题（最少的硬币拼出前面的面值 27-ak） {前两步和递归很像}

转移方程

f(x) = min{f(x-2)+1, f(x-5)+1, f(x-7)+1}

初始条件和边界情况

f(0) = 0，如果不能拼出Y，f(Y) = +∞

计算顺序

从小到大计算，f(0)，f(1)，f(2)....

leetcode 零钱兑换

题目分析：
假设有面值为 2，5，7 的三种硬币无数个，要求用最少的硬币个数凑出 27
步骤
先假定最优解的最后一个硬币面值为 ak，则之前的硬币总面值为 27-ak
则定义一个函数 f(x) ，表示构成面值 x 最少要 f(x) 个硬币
找到 f(x) 的递归定义， f(x) 是减去最后一枚硬币的面值的最小值
对特殊情况分别讨论
从小到大计算各个递归阶段的值，从而避免了递归中的重复计算

class Solution(object):
    def coinChange(self, coins, amount):
        f = [float('inf') for i in range(amount + 1)]  # 开辟从 0 到 amount 大小的数组，初始值设置为正无穷
        f[0] = 0  # 初始化 f[0] = 0 面值为 0 需要 0 个硬币
        # 这个 for 循环求凑出每一个面值最少需要多少硬币 f[1]、f[2]、f[3]...
        for i in range(1, amount + 1):  # i 代表面值，从 f[1] 开始，到 amount+1 共 amount 个数
            for j in coins:  # 遍历硬币的集合
                if i >= j and f[i - j] != float('inf'):  # 如果 i 的面值比 j 大，且要判断的数有值
                    # f[i] 的值为 构成 i 面值去掉最后一枚 coin 的面值所需的硬币数，加一（最后一枚 取最小值
                    f[i] = min(f[i - j] + 1, f[i])
        if f[amount] == float('inf'):  # 如果最后没有被更新，则说明无法构成
            f[amount] = -1
        return f[amount]


coins = [2, 5, 7]
amount = 27
s = Solution()
print(s.coinChange(coins, amount))

例 动态规划实现斐波那契数列

def f(n):  # 动态规划斐波那契函数（从 n = 1 开始）
    a = [1 for _ in range(n + 1)]  # 开辟 0 ~ n 的数组
    a[1] = 1  # 初始化第一项，注意，第 0 项不用
    if n >= 2:  # 当 n 大于等于二的时候
        for i in range(3, n + 1):  # 第三项往后满足递推关系
            a[i] = a[i - 2] + a[i - 1]
    return a[-1]  # 返回最后一项的值

# for i in range(1, 11):  # 检查前 10 项
#     print(f(i))
print(f(100))  # 直接出第 100 项的值，用暴力递归不行

【优化版本】根据分析实际进行操作的只有三个内存，所以直接用三个变量进行替代

def f(n):  # 动态规划斐波那契函数（从 n = 1 开始）
    if n == 1 or n == 2:
        return 1
    else:
        a = 1
        b = 1
        for i in range(2, n):
            sum = a + b  # 更新 c 的值
            a = b
            b = sum
    return sum  # 返回最后一项的值

例 剑指 Offer 10- II. 青蛙跳台阶问题

【分析】此问题和斐波那契数列几乎一模一样，根据上面的类比此题即可

常规动态规划版

class Solution(object):
    def numWays(self, n):  # 跳了 n 个台阶有几种跳法
        a = [1 for _ in range(n + 1)]  # 开辟数组，初始化都为 1，a[0] = 1
        if n == 1:  # 单独判断 n 为 1 的时候，防止数组溢出
            a[1] = 1
        elif n > 1:
            a[1] = 1  # 初始化前两个
            a[2] = 2
            for i in range(3, n + 1):  # 从第三位开始到最后写递推式
                a[i] = a[i - 1] + a[i - 2]
        return a[-1] % 1000000007  # 题目要求取模

【优化版本】根据分析实际进行操作的只有三个内存，所以直接用三个变量进行替代

class Solution(object):
    def numWays(self, n):  # 跳了 n 个台阶有几种跳法
        # 单独判断前三个取值
        if n == 0:  
            return 1
        elif n == 1:
            return 1
        elif n == 2:
            return 2
        # 计算一般情况
        a = 1  # 初始化
        b = 2
        for i in range(2, n):  # 执行 n-2 步迭代
            sum = a + b  # 更新 sum 的值
            a = b
            b = sum
        return sum % 1000000007

【再优化版】初始化 a，b 在一行；去掉了第三个变量 c ，直接用计算结果替换

class Solution:
    def numWays(self, n):
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b  # a = b；b = a+b
        return a % 1000000007

【数据结构】动态规划（Dynamic programming，DP）

感谢您的支持，我会继续努力的!