动态规划 = 把大问题拆成小问题 + 记住小问题的答案 + 避免重复计算
最简单的题目示例——斐波那契数列
class Solution: def fib(self, n: int) -> int: # 排除 Corner Case if n == 0: return 0 # 创建 dp table dp = [0] * (n + 1) # 初始化 dp 数组 dp[0] = 0 dp[1] = 1 # 遍历顺序: 由前向后。因为后面要用到前面的状态 for i in range(2, n + 1): # 确定递归公式/状态转移公式 dp[i] = dp[i - 1] + dp[i - 2] # 返回答案 return dp[n]
//非压缩状态的版本 class Solution { public int fib(int n) { if (n <= 1) return n; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int index = 2; index <= n; index++){ dp[index] = dp[index - 1] + dp[index - 2]; } return dp[n]; } }2、动态规划的解题步骤------以上题为例
1、确定dp数组（dp table）以及下标的含义
dp[i]就是每一项的具体值——例如dp[0]的值是0，dp[1]的值是1
2、确定递推公式
本题中递推公式已经给出状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];简单的题目可能会直接给出递推公式，较难的题目需要自己根据数学知识推导出来，
3、dp数组如何初始化
本题中也将初始化值给出，
dp[0] = 0; dp[1] = 1;
4、确定遍历顺序
遍历顺序根据题目进行推导，从公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，斐波那契数列是前两个数相加的结果赋值给后边的数所以dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前向后遍历的，也就可以简单的按顺序遍历的方法进行遍历，不同的题目可能也会有不同的遍历顺序。
5、举例推导dp数组
举例推导就是自己根据已经找到的规律写一些数值，然后设置n的值进行遍历看看是否和推导的结果相同，因为一般数学推导的前几个数值都是对的，那么当打印的结果不对时就打印dp数组如果发现和推导的数值不相同，就需要更改递推公式，或者找其他的代码错误。
3、较难的题目进行强化
1、确定dp数组（dp table）以及下标的含义
dp[i] [j] ：表示从（0 ，0）出发，到(i, j) 有dp[i] [j]条不同的路径。最后返回的dp[i] [j]就是所有不同的路径
2、确定递推公式
对于dp[i] [j]来说dp[i] [j]=dp[i-1] [j] + dp[i] [j-1]就只有这两种情况，所以这就是dp数组的递推公式
3、dp数组如何初始化
直接从最起始的位置可以看出从(0, 0)的位置到(i, 0)的路径只有一条
所以初始化代码为： for (int i = 0; i < m; i++) dp[i][0] = 1; for (int j = 0; j < n; j++) dp[0][j] = 1;
4、确定遍历顺序
根据递推公式和题目可以看出来递推之后的值是从上一个值向下或者向右推导的，所以遍历顺序就是从左到右的遍历顺序
5、举例推导dp数组
举例推导就是自己根据已经找到的规律写一些数值，根据数学等方法进行数值的推导然后与自己代码的遍历数值进行比较
public static int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; //初始化 for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; }class Solution: def uniquePaths(self, m: int, n: int) -> int: # 创建一个二维列表用于存储唯一路径数 dp = [[0] * n for _ in range(m)] # 设置第一行和第一列的基本情况 for i in range(m): dp[i][0] = 1 for j in range(n): dp[0][j] = 1 # 计算每个单元格的唯一路径数 for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # 返回右下角单元格的唯一路径数 return dp[m - 1][n - 1]
总结
动态规划是一种非常实用的算法思想，会被用来解决很多的问题，可能平常做算法的时候已经用到了这种思想，但是并没有注意，虽然以上写了一些看似固定的算法模板，但是这种算法思想仍然需要熟练的情况才能够信手拈来，如果想深入学习可以看看贪心算法，贪心和动规有一定的相似性，但是贪心是完全没有固定公式的，需要具备全面的算法思想。
