LeetCode Day动态编程第1部分

509. 斐波那契数列

斐波那契数，通常表示为 F(n)，形成一个序列，称为斐波那契数列，其中每个数都是前两个数的和，从 0 和 1 开始。即，

F(0) = 0, F(1) = 1
F(n)=F(n-1)+F(n-2)，对于n＞1 1.
给定 n，计算 F(n)。

示例1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

限制：

0 原始页面

递归法

    public int fib(int n) {
        if(n==0){
            return 0;
        }     
        else if(n==1){
            return 1;
        }   
        else{
            return fib(n-1) + fib(n-2);
        }
    }

递归法就像DFS一样，深入进行，然后回溯得到最终答案。
时间：O(2^n)
空间：O(1)

    private int[] dp = new int[31];
    public int fib(int n) {
        if(n<2){
            dp[n] = n;
            return n;
        }  

        if(n>=2 && dp[n]!=0){
            return dp[n];
        }

        dp[n] = fib(n-1) + fib(n-2);
        return dp[n];
    }

我们可以使用全局数组来保存结果，以避免相同元素的重复递归。例如下图显示 f(17) 和 f(18) 是两种不同的递归路线，如果我们使用正常的递归方法，我们必须多次计算它们。

时间：O(n)，空间：O(n)

动态规划

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

递归是从上到下再回溯，内存递归会保存递归结果，避免重复计算。现在动态规划从下到上进行，并将每一步的结果保存到 dp 数组中。
时间：O(n)
空间：O(n)

我们还可以动态更新限制数而不是数组。这将节省空间复杂度，特别是对于大量元素。

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int start = 0;
        int pre = 1;
        int res = pre;

        for(int i=2; i<=n; i++){
            res = start + pre;
            start = pre;
            pre = res;
        }
        return res;
    }

70. 爬楼梯

您正在爬楼梯。需要n步才能到达山顶。

每次您可以爬 1 或 2 级台阶。您可以通过多少种不同的方式登上顶峰？

示例1：

输入：n = 2
输出：2
说明：有两种方法可以登顶。

1. 1 步 + 1 步
2. 2步 示例2：

输入：n = 3
输出：3
说明：共有三种方法可以登顶。

1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步

70. 爬楼梯

您正在爬楼梯。需要n步才能到达山顶。

每次您可以爬 1 或 2 级台阶。您可以通过多少种不同的方式登上顶峰？

示例1：

输入：n = 2
输出：2
说明：有两种方法可以登顶。

1. 1 步 + 1 步
2. 2步 示例2：

输入：n = 3
输出：3
说明：共有三种方法可以登顶。

1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步

限制：

1 原始页面

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        } 
        return dp[n];       
    }

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }

        int prepre = 1;
        int pre = 2;
        int res = 0;
        for(int i=3; i<=n; i++){
            res = prepre + pre;
            prepre = pre;
            pre = res;
        } 
        return res;       
    }

746. 最小成本爬楼梯

给定一个整数数组 cost，其中 cost[i] 是楼梯上第 i 步的成本。支付费用后，您可以爬一层或两层台阶。

您可以从索引 0 的步骤开始，也可以从索引 1 的步骤开始。

返回到达楼层顶部的最低成本。

示例1：

输入：成本 = [10,15,20]
输出：15
说明：您将从索引 1 开始。

• 支付 15 美元，爬两级台阶即可到达顶部。 总成本是15。 示例2：

输入：成本 = [1,100,1,1,1,100,1,1,100,1]
输出：6
说明：您将从索引 0 开始。

• 支付 1 并爬两级台阶即可到达索引 2。
• 支付 1 并爬两级台阶即可到达索引 4。
• 支付 1 并爬两级台阶即可到达索引 6。
• 支付 1 并爬一级即可达到指数 7。
• 支付 1 并爬两级台阶即可到达索引 9。
• 支付1并爬一级即可到达顶部。 总费用是6。

限制：

2 0 原始页面

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length < 2){
            return 0;
        }

        int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[dp.length-1];

    }
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`

请注意，问题告诉我们可以从索引 0 和索引 1 开始，这意味着如果楼梯数小于 2，我们的成本将为 0，因为我们可以从该点开始，并且 start 的行为将成本为0，只有移动成本的行为。

以上是LeetCode Day动态编程第1部分的详细内容。更多信息请关注PHP中文网其他相关文章！