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

力扣爆刷第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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

二、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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

三、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);
    }
}
1
2
3
4
5
6
7
8
9
10
11

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

1
2
3
4
5
6
7
8
9
10
11
12
13

五、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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20