文章目录
- 1、动态规划
- 2、leetcode509:斐波那契数列
- 3、leetcode62:不同路径
- 4、leetcode121:买卖股票的最佳时机
- 5、leetcode70:爬楼梯
- 6、leetcode279:完全平方数
- 7、leetcode221:最大正方形
1、动态规划
只能向下、向右的走,从图中左上角走到右下角,有几条路径
因为只能向下、向右走,所以从起始点走到点(R,C),路径数等于,以起始点到点(R,C)为对角线的矩形里,到点(R,C)左侧点的路径数 + 到点(R,C)上边点的路径数 (动态规划的方程式)
// 动态规划的方程式 [R,C] = [R - 1][C] + [R][C - 1]
有些类似斐波那契数列了,起始点就是[0][0] (动态规划的初始状态),那递归终止的条件,就是其左侧点或者上边点不存在,此时,到它的路径只有一条,return 1,一直算到点(R,C)(动态规划的终止状态)。以上,动态规划的三要素:
- 动态规划的方程式
- 动态规划的初始状态
- 动态规划的终止状态
从起始状态(0,0),到终止状态(R,C),中间每个格子的值(到达它的路径数),都会算出来,这些中间结果,可存入一个数组,这题可用二维数组存。动态规划可用来干:
- 1)计数:有多少种方式或路径,如上面从左上角到右下角有多少路径
- 2)求最值:从左上角到右下角路径的最大数字和,每个数字不等,代表权重,求最长路径或最小路径
- 3)求存在性:是否存在某个可能,可以从A走到B
动态规划的分类:
自底向上:从最小的子问题开始,逐步计算出所有可能的状态,直到解决原问题
自顶向下:通过递归地方式,从原问题开始,依次分解为更小的子问题,通常需要记忆化搜索(Memoization)来保存已经计算过的结果,避免重复计算
2、leetcode509:斐波那契数列
不再递归了,根据方程式,步步为营,从F(2)一路计算到F(n),并把每个中间值存入数组中,最后返回数组的第n个元素即可
public class P509Two { public int recursion(int n) { //F(0)和F(1) if (n < 2) { return n == 0 ? 0 : 1; } int[] dp = new int[n + 1]; dp[1] = 1; //F(1) // 根据方程式,计算每个值,存入数组,从F(2)一路计算到F(5) for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }
3、leetcode62:不同路径
前面已经分析过了,这儿的方程式为:F(m,n)= F(m - 1,n)+ F(m,n - 1),初始状态为(1,1),终止状态为(m,n)
public class P62 { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; dp[0][0] = 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 如果是边缘,x轴或者y轴,则直接赋值1,因为只有一条路可达,其余按方程式赋值 if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } }
红圈里的这些,x轴或者y轴上的,到达他们的路径只有一条,因此直接赋值1,别用方程式去计算,会导致数组下标越界。除了这些点,其余按方程式赋值,最后返回(m-1,n-1)位置的值即可。
两道题,给我的个人感觉是,动态规划,就是从初始状态开始,根据方程式,步步为营,经过一个个中间状态的值,到达终止状态 ,最后,如果你需要存储这些中间状态值,一般用数组存储,因为其访问数据的时间复杂度为O(1)。
4、leetcode121:买卖股票的最佳时机
这题,本质就是求数组后面元素与前面元素的差值的最大值,两层for循环,默认返回为0,遇到最大的值就覆盖,即可:
public class P121 { public int maxProfit(int[] prices) { if (null == prices || prices.length < 2) { return 0; } int result = 0; for (int i = 0; i < prices.length - 1; i++) { // 注意内层循环,最快第二天才能卖出,因此,这里是i+1开始 for (int j = i + 1; j < prices.length; j++) { result = Math.max((prices[j] - prices[i]), result); } } return result; } }
优化下:遍历数组,更新前 i 天的最低买入成本,同时更新前i天的最高利润(第i天与前面i-1天最低价的差值,然后不停覆盖这个差值,取最大值)
public class P121 { public int maxProfit(int[] prices) { if (null == prices || prices.length < 2) { return 0; } int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int price : prices) { minPrice = Math.min(minPrice, price); maxProfit = Math.max(maxProfit, price - minPrice); } return maxProfit; } }
5、leetcode70:爬楼梯
参考上面62题不同路径的思想:
- 62题:到(m,n)的路径数 = 到(m,n)上方点的路径数 + 到(m,n)左侧点的路径数,因为规定了只能向下、向右移动
- 本题:到n阶的路径数 = 到n - 1阶的路径数 + 到 n - 2阶的路径数,因为一次只能走一个或者两个台阶
切入点:动态规划要经过状态转移,那就该想一下,题中要求的状态,怎么可以由上一步到达
由此,动态规划方程式为:
f(n) = f(n - 1) + f(n - 2)
代码实现:
public class P70 { public int climbStairs(int n) { if (n <= 0) { return 0; } int[] resultArr = new int[n + 1]; resultArr[0] = 1; resultArr[1] = 1; for (int i = 2; i < n + 1; i++) { resultArr[i] = resultArr[i - 1] + resultArr[i - 2]; } return resultArr[n]; } }
优化下,不存中间值了,因为万一n很大,很浪费内存,而且题目只要最后的值,不需要中间结果
public class P70 { public int climbStairs(int n) { if (n <= 0) { return 0; } // f(x-1) int pre = 1; // f(x-2) int prePre = 0; int result = 1; for (int i = 1; i <= n ; i++) { result = pre + prePre; // 状态转移,往前走一步,f(x-2)变成了新的f(x-1),f(x-1)变成了f(x) prePre = pre; pre = result; } return result; } }
6、leetcode279:完全平方数
思路一:暴力解法
根据四平方和定理,这题返回的结果肯定是1、2、3、4里的一个。那我找:n是否能由1个平方数搞出来,不行就看是否能由2个平方数搞出来,最多到4,封顶了就。因为这题求的是最少的数量,别说n = 1 + 1 + 1 + …… + 1。借助以下四条数学规律:
实现:
public class P279 { public int numSquares(int n) { // 消除4的因子 while (n % 4 == 0) { n = n / 4; } // %8 == 7,一定是4 if (n % 8 == 7) { return 4; } // 找a和b两个数,使得n = a^2 + b^2,且a和b这些数必然落在区间 [1,根号n]之间 for (int a = 0; a * a <= n; a++) { int b = (int) Math.sqrt(n - a * a); if (a * a + b * b == n) { // 找到a,b了,如果a或者b是0,说明a^2 = n或者b^2 = n,返回1,反之,返回2 return (a > 0 && b > 0) ? 2 : 1; } } // 不是1,也不是2,那就是3 return 3; } }
思路二:动态规划
用几个数的平方的和表示数字n,这几个平方数一定在[1,根号n]
之间,因为根号n的平方就是n了。从1到根号n的范围,遍历,假设遍历到了数字 j,此时剩下 n - j * j ,n - j * j 的平方数字的数量假设为f(n - j * j ),那f(n)就是这个值 + 1,状态转移方程:
f(n) = f(n - j * j ) + 1
当然,这题找最小数量,因此,取的是[1,根号n],最小的平方数的数量,代码实现:
public class P279 { public int numSquares(int n) { int[] resultArr = new int[n + 1]; // 算从1到n,每个数的平方数的数量 for (int i = 1; i <= n; i++) { int minn = Integer.MAX_VALUE; // j * j <= i,即从1到根号n的范围 for (int j = 1; j * j <= i; j++) { minn = Math.min(minn, resultArr[i - j * j]); } resultArr[i] = minn + 1; } return resultArr[n]; } }
7、leetcode221:最大正方形
用 dp(i,j) 表示以 (i,j) 为右下角
,且只包含 1 的正方形的边长最大值,那这个dp值,应该取决于其左边、上边、右上方三个点的dp值,如下图:
红色方框所在的点(2,3),其dp值,取决于黄色方框里的三个点的dp值,且是像短板水桶一样,全是1的正方形的最大边长,得看这三个点dp的最小值,得出状态转移方程式为:
dp(i, j) = min ( dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1) ) + 1
代码实现:
public class P221 { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } // 最大边长 int maxSide = 0; // 矩阵行列数 int row = matrix.length; int col = matrix[0].length; int[][] dp = new int[row][col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (matrix[i][j] == '0') { // 值为0,则不存在全为1的正方形,int默认值就是0,这里不赋值也行 dp[i][j] = 0; } else { // 在x轴或者y轴边上,那以其为右下角的正方形,就只能是自己那一块,dp = 1 if (i == 0 || j == 0) { dp[i][j] = 1; } else { // 否则就走正常的状态转移方程 dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } } // 求整个矩阵中,每个点的dp的最大值 maxSide = Math.max(maxSide, dp[i][j]); } } return maxSide * maxSide; } }