• home > theory > algorithm > leetcode >

    DP笔记(5):递推型动态规划概念性总结

    Author:zhoulujun Date:

    ​ 动态规划是一种求最优化递推问题,动态规划中涉及到决策过程; 所以动态规划是递推问题的子问题;

    DP对很多新手来说非常可怕,而递推和递归就比较简单。

    递推型动态规划

    动态规划是一种求最优化递推问题,动态规划中涉及到决策过程; 所以动态规划是递推问题的子问题。

    让我们不管DP,先了解了解递推和递归。

    前置知识: 

    • 递推在数学中很常用,概念也和数学中的一样,靠循环解决(如杨辉三角、标数法、递推数列等)

    • 递归就和数学中的递推归纳不同了。

    在计算机中

    • 递归指像DFS这样的,在函数中自己调用自己的写法(像阿克曼函数)。简而言之,递推就是从小到大一个一个算出结果,最后得到答案。

    • 递归则是从大到小一层一层往下钻,求出算最终答案需要的东西。这两者其实都很简单。

    DP 其实就是 递推和递归的升级版本。递推和递归 中几个维度的变量(如递推数列的下标、上楼梯和标数法的行、列等)都是题目中直接地,明显地告诉了你的;而DP 的维度是我们自己 生造出来的,题目中没有明确说到的(如01背包的序号和体积)。因此,DP 就会比 递推、递归难想,隐蔽许多。同时 DP 也是生造维度情况下 递推和递归的统称。所以,DP 涵盖了 递推和递归的思想。这是它的又一个难点。此外,DP 的每一次递推也可以看成一次 决策。例如,在背包问题中,每一次递推就相当于做了一次选与不选的 决策。

    数学归纳法:

    1. 验证k0 成立;  (边界条件)

    2. 证明如果ki 成立,那么Ki+1 也成立;(推导公式)

    3.  联合a & b, 证明k0 -> kn 成立;

    递推问题的步骤:

    确定递推公式时候,不要管前一个结果如何得到

    1. 确定递推状态(状态方程,学习重点): 一个函数符号f(x), 以及函数符号的含义描述; 确定自变量x(影响结果的因素有哪些), 因变量y;

    2. 确定递推公式(ki -> ki+1) ,取决于递推状态的定义;(这里ki 是第i组对应的满足题意的结果,不要纠结与它怎么得到的!)

    3. 分析边界条件;

    4. 程序实现: 递归 或者 循环

    递推 与 动态规划 之间的关系:

    a. 动态规划是一种求最优化递推问题,动态规划中涉及到决策过程; 所以动态规划是递推问题的子问题;

        其中 递推公式 在动态规划中叫做 状态转移方程, 具体步骤与上面递推是类似的;

    b. 在状态转移方程中,主要下面三个重点:

        状态定义:

        决策过程:从所有可能中选择最优解;  //如果不涉及决策,大概率就是贪心算法;

        阶段依赖:当前阶段只依赖上一阶段; 对于不同问题中,阶段概念是一个很宽泛的定义;

    c. 在实际求解问题过程中,有两种方向:处理问题中,如果从哪里来的条件判断比较复杂,那就可以考虑到哪里去的方法;

        从哪里来:当前状态 = f(前一个状态 ) ; 当前这个状态(被推导) 可以通过其他状态推导得到;

        到哪里去:每更新当前状态时 ==> 主动更新可以从它推导出状态的结果; 当前这个状态(去推导)可以到达哪些状态;

    这两种方向,本质是一样的,底层是一个图的结构, 递推(动归) 求解顺序就是状态依赖图的一个拓扑序,对有向图的一维化序列化的结果;

    d. 动归典型题: 体会从哪里来,到哪里去的精髓;

    DP、递推和递归的优劣

    递推和递归 具体的分析如下图,而 DP 可以类比进行分析。

    DP、递推和递归的优劣

    只要 深度理解了递推和递归(尤其是递推),学习DP就相对轻松 了。

    为什么不用递归?

    当我们在递归地寻找每个子问题的最优解的时候,有可能会重复地遇到一些更小的子问题,而且这些子问题会重叠地出现在子问题里,出现这样的情况,会有很多重复的计算,动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候,动态规划可以减少很多重复的计算。

    去掉重复子问题不是保证解的正确性必须的,但是如果递归求解子问题时,没有出现重复子问题,则没有必要用动态规划,直接普通的递归就可以了。

    解决动态规划问题的核心

    解决动态规划问题的核心是找出子问题及其子问题与原问题的关系

    动态规划算法中关于最优子结构和重复子问题的理解的关键点:

    1. 证明问题的方案中包含一种选择,选择之后留下一个或多个子问题;

    2. 设计子问题的递归描述方式;

    3. 证明对原问题的最优解包括了对所有子问题的最优解;

    4. 证明子问题是重叠的(这一步不是动态规划正确性必需的,但是如果子问题无重叠,则效率与一般递归是相同的)。

    解决动态规划问题的步骤

    动态规划有两种计算顺序,一种是自顶向下的、使用备忘录(记忆化)的递归方法,一种是自底向上的、使用DP数组(滚动数组)的循环方法。不过在普通的动态规划题目中,99% 的情况我们都不需要用到备忘录方法,所以我们最好坚持用自底向上的DP数组。同时备忘录方法的空间复杂度会比较高。

    自顶向下

    递归的解法需要非常多的重复计算,如果有一种办法能避免这些重复计算,可以节省大量计算时间。记忆化就是基于这个思路的算法。在递归地求解子问题f(1),f(2)... 过程中,将结果保存到一个表里,在后续求解子问题中如果遇到求过结果的子问题,直接查表去得到答案而不计算。

    自底向上

    有了状态转移方程,我们就知道如何从最小的问题规模入手,然后不断地增加问题规模,直到所要求的问题规模为止。在这个过程中,我们可以从小到大记忆每个问题规模的解来避免重复的计算。这种方法就是自底向上的方法,由于避免了递归,这是一种更好的办法。

    但是迭代法需要有一个明确的迭代方向,例如线性,区间,树形,状态压缩等比较主流的动态规划问题中,迭代方向都有相应的模式。但是有一些问题迭代法方向是不确定的,这时可以退而求其次用记忆化来做。

    动态规划自底向上的四个解题步骤是:

    1. 定义子问题

    2. 写出子问题的递推关系

    3. 确定 DP 数组的计算顺序

    4. 空间优化(可选)



    常见递推关系式

    常见状态

    1. 坐标型

    2. 前缀划分型

    3. 前缀匹配型

    4. 区间型

    5. 背包型

    坐标型
    • dp[i]:从起点到坐标 i 的最值/方案数/可行性

    • dp[i][j]:从起点到坐标 i, j 的最值/方案数/可行性

    前缀划分型
    • dp[i]:前 i 个字符的最值/方案数/可行性

    • dp[i][j]:前 i 个字符划分为 j 个部分的最值/方案数/可行性

    前缀匹配型
    • dp[i][j]:第一个字符串的前 i 个字符匹配上第二个字符串的前 j 个字符的最值/方案数/可行性

    区间型
    • dp[i][j]:区间 i-j 的最值/方案数/可行性

    背包型
    • dp[i][j]:前 i 个物品里选出一些物品组成和为 j 的大小的最值/方案数/可行性

    常见递推关系式

    动态规划虽然飘逸,但还是有规律可循,前人还是总结了好几种常见的递推关系模式。

    动态规划算法有三个要素:
    • 所有不同的子问题所组成的表(它包含的问题数目称为问题的大小,即 size);

    • 问题解决的依赖关系可以看成是一个图;

    • 填充子问题的顺序(实际上就是(2)所得到的图的一个拓扑排序)。

    关系具体推荐阅读《动态规划三:常见状态与常见递推关系式


    参考文章:

    只要 深度理解了递推和递归(尤其是递推),学习DP就相对轻松 了。 https://www.acwing.com/blog/content/12717/

    递推与动态规划 https://www.cnblogs.com/ChunboBlog/p/16094011.html

    【力扣刷题】动态规划问题的思考与总结 https://star2dust.github.io/post/leecode-dynamic-programming/



    转载本站文章《DP笔记(5):递推型动态规划概念性总结》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9113.html