[数据结构与算法]力扣算法学习day26-3

力扣算法学习day26-3

509-斐波那契数

题目

代码实现

class Solution {
    // public int fib(int n) {
    //     if(n < 2){
    //         return n;
    //     }
    //     int result = dp(0,1,n-1);
    //     return result;
    // }
    // public int dp(int one,int two,int sum){
    //     if(sum == 0){
    //         return two;
    //     }

    //     int result = one + two;
        
    //     return dp(two,result,sum-1);
    // }

    // 代码随想录，dp规范个人练习
    public int fib(int n) {
        if(n < 2){
            return n;
        }
        // 1.定义dp数组
        // 2.确定递推公式(即状态转移方程) 这里题直接给出：dp[i] = dp[i-1] + dp[i-2];
        int[] result = new int[n+1];

        // 3.初始化dp数组
        result[0] = 0;
        result[1] = 1;

        // 4.确定遍历顺序
        for(int i = 2;i <= n;i++){
            result[i] = result[i-1] + result[i-2];
        }

        // 5.举例推导dp数组的答案 比如实例1应该是result[2] = 1.
        return result[n];
    }
}

70-爬楼梯

题目

代码实现

class Solution {
    // 0ms
    // public int climbStairs(int n) {
    //     if(n < 3){
    //         return n;
    //     }
    //     // dp
    //     // 1.初始化dp数组
    //     int[] dp = new int[n];

    //     // 2.找递归公式：比如第三层，第一层跨2步能够到第三层，第二层跨1步能够到第三层
    //     // 用1,2标识是为了突出这两种情况，所以第一层的情况+第二层的情况=第三层的情况
    //     // 所以递归公式：dp[i] = dp[i-1] + dp[i-2];
    //     // 3.初始化dp数组
    //     dp[0] = 1;
    //     dp[1] = 2;

    //     // 4.找递归的顺序
    //     for(int i = 2;i < n;i++){
    //         dp[i] = dp[i-1] + dp[i-2];
    //     }

    //     // 5.略
    //     return dp[n-1];
    // }

    // 进阶思考:对于n阶楼梯，每次可以爬1-m个台阶问题的思考
    int climbStairs(int n,int m) {
        // int m = 2;// 实验m=2本题是否成立,需要去掉输入的int m，结果通过 3ms
        // 创建dp数组
        int[] dp = new int[n];

        // 递归公式：i > m 由上面那道题很容易推出：dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-m]
        //          i <= m,dp[i] = d[i-1] + d[i-2] + ... + d[0] + 1(本身)
        // 初始化
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            if(i < m){// 我这里0是第一层
                for(int j = 1;j <= i;j++){
                    dp[i] += dp[i-j];
                }
                dp[i]++;// 加上一步到位的情况
            } else{// i > m
                for(int j = 1;j <= m;j++){
                    dp[i] += dp[i-j];
                }
            }
        }

        for(int i = 0;i < n;i++){
            System.out.println(dp[i]);
        }
        return dp[n-1];
    }
}