【数据结构】动态规划(Dynamic programming,DP)

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

  1. 计数
  • 有多少种方式走到右下角
  • 有多少种方法选出 k 个数使得和是 Sum
  1. 求最大最小值
  • 从左上角走到右下角路径的最大数字和
  • 最长上升子序列长度
  1. 求存在性
  • 取石子游戏,先手是否必胜
  • 能不能选出 k 个数使得和是 Sum

最值型解题步骤

  1. 确定状态
  • 最后一步(最优策略中使用的最后一枚硬币 ak)
  • 化成子问题(最少的硬币拼出前面的面值 27-ak) {前两步和递归很像}
  1. 转移方程
  • f(x) = min{f(x-2)+1, f(x-5)+1, f(x-7)+1}
  1. 初始条件和边界情况
  • f(0) = 0,如果不能拼出Y,f(Y) = +∞
  1. 计算顺序
  • 从小到大计算,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
赞赏