[Algorithm][动态规划][动态规划原理][整体理解]详细讲解
0.前言
- 本节非常重要哦，有关后面动态规划题的总体理解
- 建议和后面的题搭配起来食用哦~
1.动态规划一般思路
- 创建
dp表- 可能是一维数组，也可能是二维数组
- 确定状态表示 ->
dp[i]的含义 - 推导状态转移方程 ->
dp[i] = ?- 用之前或之后的值，推导出
dp[i]的值 - 根据最近的一步，来划分问题
- 用之前或之后的值，推导出
- 初始化：保证填表的时候不越界
- 确定填表顺序：为了保证填写当前状态的时候，所需要的状态已经计算过了
- 确定返回值
- 题目要求 + 状态标识
2.状态表示如何来？
- 题目要求
- 经验 + 题目要求
- 一维线性
dp- 以
i位置为结尾 - 以
i位置为起点
- 以
- 一维线性
- 分析问题的过程中，发现重复子问题
3.状态转移方程如何推导？
- 简单问题可以直接写出状态转移方程
- 复杂问题，多个状态时，可以画图表示各个状态的关系，最后对着关系机写出状态转移方程
4.处理边界问题以及初始化问题的技巧
-
虚拟结点如何开？
-
一维：
dp表多开一位- 注意事项：
- 虚拟节点里面的值，要保证后面填表时是正确的
- 下标的映射关系
- 注意事项：
-
二维：
dp表多开一行和一列- 注意事项：
- 虚拟节点里面的值，要保证后面填表时是正确的
- 下标的映射关系
- 注意事项：
-
-
算法里面初始化为无穷：
INT_MAX || INT_MIN时，要注意潜在的溢出风险- 替换为
0x3f3f3f3f || -0x3f3f3f3f即可解决该问题 - 首先它足够大，其次它没有溢出风险
- 替换为
-
多个状态方程，其中只有一部分的状态方程需要特殊的初始化，那么可以想办法把这个状态方程拆成多步，分步执行，尝试避免特殊处理初始化
-
根据实际情况，可以考虑将dp表中的值，都初始化为最次的情况
- 这样处理或许可以省去一些步骤
-
关于字符串dp问题，空串是有研究意义的
- 引入空串后，会方便初始化
- 倘若在
dp表中加入了虚拟结点，那么可以在初始化时，在源字符串前面加上' '- 这是为了确保字符串下标正确，避免在字符串中找子串时不必要的麻烦
5.空间优化思路
- 优化方法：
- 滚动数组
- 优化效果：
- O ( N 2 ) − > O ( N ) O(N^2) -> O(N) O(N2)−>O(N)
- O ( N ) − > O ( 1 ) O(N) -> O(1) O(N)−>O(1)
6.子序列 vs 子数组
- 子序列：
- 相对顺序是跟源字符串/数组是一致的
- 但是元素和元素之间，在源字符串/数组中可以是不连续的
- 一般时间复杂度： O ( 2 n ) O(2^n) O(2n)
- 子数组：
- 在源字符串/数组中挑出来，必须是连续的
- 一般时间复杂度： O ( N 2 ) O(N^2) O(N2)
- 子序列其实相当于包含了子数组