0x10 什么是动态规划
0x11 前提
动态规划所解问题的一般形式是求最值,而求最值,肯定要把所有可行的答案穷举。所以动态规划的核心思想就是穷举求最值。但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事
1. 首先需要你熟练掌握递归思维,只有列出正确的状态转移方程,才能正确地穷举。
2. 而且,你需要判断算法问题是否具备最优子结构,是否能够通过子问题的最值得到原问题的最值。
3. 另外,动态规划问题存在重叠子问题,如果暴力穷举的话效率会很低,所以需要你使用memo
或者dpTable
来优化穷举过程,避免不必要的计算。
Tip: 这三步是穷举的思考方式,不是DP专属
注:计数、存在性等非最优化问题的递推解法也常被称作$DP$,这里一并列出,可以作为广义$DP$ 的一部分Ref
0x12 基本概念
- 状态
- 阶段(一个阶段可以有一个或多个状态)
- 决策
Ref
0x13 本质
- 静态
状态空间中的点,被多个其他点依赖(重叠子问题),利用空间换时间的方式,将每个算出的状态解记录下来(空间),避免重复计算(时间) - 动态
动态规划的求解过程,就是对状态空间的遍历,根据无后效性,会构成一个有向无环图,求解/遍历的顺序就是该有向无环图的一个拓扑序。在有向无环图中,节点对应问题的状态,有向边对应状态之间的转移,转移时作出的选择就是决策。Ref1 Ref2
状态中的一个维度用于划分阶段(阶段一定是有序的,或者可以排序的Ref),其余维用于附加信息,以至于在状态转移时,状态转移有唯一的方案,而不需要做
if
判断Ref。
从这个角度看,线性DP、树形DP、图上DP的区别并无必要(在外网并检索不到),只是树/图和遍历图(有向无环图)存在一定的同构性。(虽无必要,但这篇博客仍然值得一看:Ref)
P.S. 可以通过这道题目体会:树上1维成本01背包: 从dfs到DP到优化
0x14 两种实现
- 用
memo
自顶向下递归 【自顶向下的思维方式,是计算思维最重要的一环】 - 用
dpTable
自底向上递推【涉及滚动数组、状态压缩等空间优化】
0x20 四个步骤
- 确定状态(最后一步【状态迁移图(动宾)】、子问题【状态的函数值】)
所谓状态[i][j]
,更准确的说是实现/满足这个状态的方案,是一个集合;
状态的函数值f[i][j]
,就是该集合的一个特征值,比如该集合内元素某性质的极值(一、最值)、该集合的大小(二、计数)、该集合是否有元素(三、存在性) - 转移方程【如何综合子问题的结果】(数学上一般:子问题和迁移路径
&&
,不同子问题之间||
)
注意:数学表达式的编程实现就是通过循环展开。若针对具体问题数学表达式或可简化,则编程也得以简明 - 初始条件和边界情况
- 计算顺序(标准:子问题已求解)【用
memo
自顶向下递归不需要,用dpTable
自底向上递推才需要】这四步和动态规划无关,最优化的问题基于状态空间遍历,都使用这个方法思考,只是在存在子问题重叠时,使用
memo
或者dpTable
进行剪枝优化
0x30 入门例题 Ref
0x31 求最值:找硬币 Coin Change
我的答案
- 一定要注意边界值的处理逻辑上是$\infty$,但是代码中通过
if
条件实现 - 涉及$\infty$,一定要考虑是否有加法溢出的情况
class Solution {
public:
/**
* @param coins: a list of integer
* @param amount: a total amount of money amount
* @return: the fewest number of coins that you need to make up
*/
int coinChange(vector<int> &coins, int amount) {
int choices = coins.size();
int f[amount+1]; f[0]=0;
for(int i=1; i<=amount; i++){
f[i] = INT_MAX;
for(int j=0; j<choices; j++){
if(i-coins[j]>=0 && f[i-coins[j]]!=INT_MAX) //边界处理,与溢出处理
f[i] = min(f[i], f[i-coins[j]]+1);
}
}
if(f[amount]==INT_MAX) return -1;
else return f[amount];
}
};
0x32 计数:不同的路径 Unique Paths
我的答案
- 计数的加法原理有两个前提:不遗漏、不重复
dfs+memo
class Solution {
public:
/**
* @param m: positive integer (1 <= m <= 100)
* @param n: positive integer (1 <= n <= 100)
* @return: An integer
*/
int f[1000][1000];
int dfs(int i, int j){
if(f[i][j]!=-1) return f[i][j];
if(i==0) return f[i][j]=1;
int res = dfs(i-1,j);
if(j-1>=0) res += dfs(i, j-1);
return f[i][j]=res;
}
int uniquePaths(int m, int n) {
// write your code here
memset(f, -1, sizeof f);
return dfs(m-1,n-1);
}
};
递推+dpTable
class Solution {
public:
/**
* @param m: positive integer (1 <= m <= 100)
* @param n: positive integer (1 <= n <= 100)
* @return: An integer
*/
int uniquePaths(int m, int n) {
int f[m][n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0){ f[i][j]=1; continue;}
f[i][j] = f[i-1][j];
if(j-1>=0) f[i][j]+=f[i][j-1];
}
}
return f[m-1][n-1];
}
};
当然初始化方式不同,递推过程会有略微区别
class Solution {
public:
/**
* @param m: positive integer (1 <= m <= 100)
* @param n: positive integer (1 <= n <= 100)
* @return: An integer
*/
int uniquePaths(int m, int n) {
int f[m][n];
f[0][0]=1;
for(int i=0; i<m; i++) f[i][0] = 1;
for(int j=0; j<n; j++) f[0][j] = 1;
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
f[i][j] = f[i][j-1] + f[i-1][j];
}
}
return f[m-1][n-1];
}
};
0x33 存在性:跳跃游戏 Jump Game
我的答案
- 注意数学表达式的编程实现
class Solution {
public:
/**
* @param m: positive integer (1 <= m <= 100)
* @param n: positive integer (1 <= n <= 100)
* @return: An integer
*/
int uniquePaths(int m, int n) {
int f[m][n];
f[0][0]=1;
for(int i=0; i<m; i++) f[i][0] = 1;
for(int j=0; j<n; j++) f[0][j] = 1;
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
f[i][j] = f[i][j-1] + f[i-1][j];
}
}
return f[m-1][n-1];
}
};