之前刷力扣都在刷日题，一段时间后感觉刷题有一点感觉了，但是收获不是很系统，近期决定做一段时间的专题，第一个专题就决定是动态规划。

定义

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。 以上是百度给出的定义， 没什么参考价值。其实按我个人理解，动态规划是一种用空间换时间的策略，记录之前的结果，状态转换方程利用之前的结果，然后快速得到答案。
DP的思想与分治法类似，都是把待求解的问题分解为多个子问题，不同的是适用于DP的问题往往不是互相独立的，有些子问题会被重复计算很多次。DP的做法是这些已经解决的子问题答案保存下来。

引例：

斐波那契数列

int Fibonacci(int n) {
	//0,1,1,2,3,5,8,...
	//返回数列中第n个数
	if(n==1 || n==2) return n-1;  //边界情况
	int dp[n];  //记录方式
	dp[0] = 0, dp[1] = 1;   //初始化
	for(int i = 2; i<n; i++) {  //运算顺序
		dp[i] = dp[i-1] + dp[i-2];  //状态转换方程
	}
	return dp[n-1];
}

这个题目就是利用了简单的DP思想，是实际上这个题不需要数组，因为只用到了dp[i-1]和dp[i-2]，且最后不需要遍历找出最优，可以直接用两个变量代替，类似“滚动数组”。

核心问题

对于动态规划的核心问题，我个人总结为4点：

1. 找到合适的记录方式
2. 找到状态转换方程
3. 找到初始方法
4. 找到运算顺序

展开来谈：

找记录方式

之前说DP一空间换时间，实际上就是指DP记录之前的运算结果并运用到新的计算当中。这就要求能够找到合适的记录方法，利用合适的记录方法将之前结果保存下来。

在近期刷题的经验中，发现DP会有很大概率与字符串相关，例如：

• 最长回文子串
• 正则表达式匹配
• 最长有效括号

等等，都是DP的经典题目，实际上还会包括一些类似背包题目的其他问题。

通常，DP会利用二维数组dp[i][j]记录从i到j的某些结果，或是一维数组dp[i]表示以i为开头或结尾的一些结果，之后按一定顺序转移计算。

其中需要注意题目中给出的变量的范围，我自己就遇到过选择了过大的二维数组然后发生溢出的错误。

找到状态转换方程

决定了DP的记录方式以后，便需要通过对题目观察找到巧妙的状态转换方程，举个例子，一般dp[i][j]的转换方程可能利用到i+1、j-i这样的邻近结果，所以一般寻找时也需要从假设已知的状态写起。同时，要注意很多题目中状态转换方程存在条件变化，在不同的条件情况（例如str[i]==str[j]和str[i]!=str[j]）下，状态转换方程也会有所不同。

找到初始化方法

有了状态转换方程，初始化方法就会比较轻松，一般是找到一些边界值，例如长度为n的字符串，常常会定义n+1的数组，下标0对应边界值；或是找到一些规律，例如二维数组对角线上的值和边界的值。这个过程往往需要从状态转换方程中找到灵感。

找到运算顺序

同样，有了状态转换方程，运算顺序也比较好判断，假设dp[i][j]记录从i到j是否回文，实际上我们只用到了上三角的部分，有状态转换方程：

dp[i][j]=dp[i+1][j-1] && str[i]==str[j]

其中对角线的值为初始值，要知道dp[i][j]，实际上就是找对应矩阵上三角中 下一行前一列 的值。
在i固定的前提下，要确定j，就需要知道它前一个值，所以j的顺序必然是从前到后；
而对每一个i，要知道他的后一个值，所以应当从后往前运算。
之后就是实际的运算过程，在这个过程中，还需要注意一些边界情况。

能用动态规划解决问题的特点[1]

能采用动态规划解决的问题，一般要具有三个性质：

1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

在理解了以上要点后，个人觉得就应该多刷题去总结自己的经验了。

---

动态规划有「选或不选」和「枚举选哪个」这两种基本思考方式。在做题时，可根据题目要求，选择适合题目的一种来思考。
https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/solutions/2392051/ji-bai-100cong-di-gui-dao-di-tui-dao-you-dxz5/

参考

• [1] 知乎：动态规划