动态规划

概念

动态规划(英语：Dynamic programming，简称 DP)，是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

动态规划常常适用于有重叠子问题和最优子结构性质的问题

适用情况

动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题

  • 最优子结构: 如果某条路径是起点到终点的最短路径，则起点到该路径上的每一点都是最短路径，一个最优化策略的子策略总是最优的，最优化原理是动态规划的基础
  • 无后效性: 当前选择任何一条边都不会影响以后选择其他边，如果当前选择会影响后面的选择则不适用，每个状态都是过去历史的一个完整总结

动态规划解题的步骤

  1. 找出最优子结构
  2. 写出动态规划方程
  3. 使用自底向上或者自顶向下的方法求解
  4. 逆推求解

小结

动态规划的适用条件任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用

同样,动态规划也并不是万能的，适用动态规划的问题必须满足最优化原理和无后效性

动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略

动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率往往是比较高的，这样在时间上溢出的可能性不大

相反地，动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性

但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的

另一方面，动态规划的高时效性往往要通过大的测试数据体现出来(以与搜索作比较)，因而，对于大规模的问题如何在基本不影响运行速度的条件下，解决空间溢出的问题，是动态规划解决问题时一个普遍会遇到的问题

时空矛盾

  • 一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑，仅仅存储必不可少的内容，以及数据存储范围上精打细算(按位存储、压缩存储等)，当然这要因问题而异，进行分析，另外，在实现动态规划时，一个我们经常采用的方法是用一个与结点数一样多的数组来存储每一步的决策，这对于倒推求得一种实现最优解的方法是十分方便的，而且处理速度也有一些提高
  • 但是在内存空间紧张的情况下，我们就应该抓住问题的主要矛盾。省去这个存储决策的数组，而改成在从最优解逐级倒推时，再计算一次，选择某个可能达到这个值的上一阶段的状态，直到推出结果为止。这样做,在程序编写上比上一种做法稍微多花一点时间，运行的时效也可能会有一些(但往往很小)的下降，但却换来了很多的空间。因而这种思想在处理某些问题时,是很有意义的

案例

🐸青蛙跳阶

题目

动态规划详解

思路

  • 递归: 青蛙🐸跳阶可以使用递归求解
  • 带记忆的递归: 而递归求解中存在大量的重复计算，可以引入状态记忆，避免大量的重复计算
  • 递推: 除了递归方式，也可以使用递推的方式计算，目标是算出F(1)、F(2)…F(N)，只需要两个状态变量存储
  • 动态规划: 使用动态规划的方式，拆分子问题，记住过往，减少重复计算，关键在于状态转移转矩阵计算状态转移

求解

打家劫舍

https://leetcode.cn/problems/house-robber/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def run():
    samples = [[1, 2, 3, 1], [2, 7, 9, 3, 1]]

    for sample in samples:
        one, two = sample[0], sample[1]  # 表示n-2位置处的最大价值 和 n-1位置处的最大价值
        res_sum = max(one, two)
        for idx, s in enumerate(sample[2:], start=2):
            # n-2位置处的最大价值+n位置处的价值 和 n-1位置处的最大价值
            res_sum = max(one + s, two)
            one, two = two, res_sum
        print(res_sum)
        
	# 暴力法验证
    for sample in samples:
        idx_lst = gen_bin(n=len(sample))
        res_sum = max([sum([sample[idx] for idx, i in enumerate(bin(idx)[2:][::-1]) if int(i) == 1]) for idx in idx_lst])
        print(res_sum)

def gen_bin(n: int):
    """ 列出所有可能性 """
    n = 1 << n
    res = []
    while n := n - 1:
        if '11' not in bin(n):
            res.append(n)
    return res