力扣爆刷第126天之动态规划五连刷(斐波那契、爬楼梯、不同路径)
文章目录
- 力扣爆刷第126天之动态规划五连刷(斐波那契、爬楼梯、不同路径)
- 一、509. 斐波那契数
- 二、70. 爬楼梯
- 三、746. 使用最小花费爬楼梯
- 四、62. 不同路径
- 五、63. 不同路径 II
一、509. 斐波那契数
题目链接:https://leetcode.cn/problems/fibonacci-number/description/
思路:斐波那契数,具有很明显的动态规划的性质,状态转移方程就是斐波那契的运算公式,每一个元素都依赖于前两个元素,从而确定递推公式。
class Solution {public int fib(int n) {if(n < 2) return n;int a = 0, b = 1, c = 0;for(int i = 2; i <= n; i++) {c = a + b;a = b;b = c;}return c;}
}
二、70. 爬楼梯
题目链接:https://leetcode.cn/problems/climbing-stairs/description/
思路:本题的解法和斐波那契一模一样,问爬楼梯有多少种不同的方法,因为步长只有1步和2步,那么到达第N阶,可以从第N-1阶走1步,也可以从第N-2阶走2步,那么达到第N阶的方法数,就是第N-1阶的方法数+第N-2阶的方法数。
dp[i] = dp[i-1] + dp[i-2]
class Solution {public int climbStairs(int n) {if(n < 3) return n;int a = 1, b = 2, c = 0;for(int i = 3; i <= n; i++) {c = a + b;a = b;b = c;}return c;}
}
三、746. 使用最小花费爬楼梯
题目链接:https://leetcode.cn/problems/min-cost-climbing-stairs/description/
思路:花费最小代价爬楼梯,每次只能爬1步或者2步,定义dp[i]表示到达nums[i]时所花费的最小值,故状态转移方程为dp[i] = nums[i]+Math.min(dp[i-1], dp[i-2])。初始化dp[0]=nums[0],dp[1]=nums[1]。最后的结果为倒数两个位置的最小值,因为倒数第二位可以走走两步越过终点。
class Solution {public int minCostClimbingStairs(int[] cost) {int a = cost[0], b = cost[1], c = b;for(int i = 2; i < cost.length; i++) {c = cost[i] + Math.min(a, b);a = b;b = c;}return Math.min(a, b);}
}
四、62. 不同路径
题目链接:https://leetcode.cn/problems/unique-paths/description/
思路:求不同路径,定义dp[i][j]表示,达到num[i][j]处有几种方法,每次只能往右方或者下方走一步,所以dp[i][j]依赖的是dp[i][j-1]和dp[i-1][j]故,dp[i][j]=dp[i][j-1]+dp[i-1][j]。
class Solution {public int uniquePaths(int m, int n) {int[] dp = new int[n];dp[0] = 1;for(int i = 0; i < m; i++) {for(int j = 1; j < n; j++) {dp[j] += dp[j-1];}}return dp[n-1];}
}
五、63. 不同路径 II
题目链接:https://leetcode.cn/problems/unique-paths-ii/description/
思路:本题和上题状态转移方程都是一样的,只需要注意有石头的地方把它设置为0;
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length, n = obstacleGrid[0].length;int[] dp = new int[n];for(int i = 0; i < n; i++) {if(obstacleGrid[0][i] == 1) break;dp[i] = 1;}for(int i = 1; i < m; i++) {for(int j = 0; j < n; j++) {if(obstacleGrid[i][j] == 1) {dp[j] = 0;}else if(j != 0) {dp[j] += dp[j-1];}}}return dp[n-1];}
}