力扣爆刷第126天之动态规划五连刷（斐波那契、爬楼梯、不同路径）

一、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];}
}