动态规划的入门解析

动态规划 把大问题拆成小问题 记住小问题的答案 避免重复计算最简单的题目示例——斐波那契数列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]的值是0dp[1]的值是12、确定递推公式本题中递推公式已经给出状态转移方程 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]总结动态规划是一种非常实用的算法思想会被用来解决很多的问题可能平常做算法的时候已经用到了这种思想但是并没有注意虽然以上写了一些看似固定的算法模板但是这种算法思想仍然需要熟练的情况才能够信手拈来如果想深入学习可以看看贪心算法贪心和动规有一定的相似性但是贪心是完全没有固定公式的需要具备全面的算法思想。