【杂题】剑指 Offer 10- II. 青蛙跳台阶问题

共以下 5 个回答

• 陆狗陆狗 普通 2025年1月7日 上午9:22

  解题思路
  – 普通的dp，只是需要注意一下边界条件
  【题解1】

  class Solution {
      public int trainWays(int num) {
          // 【错误】边界问题,并且dp[0]=1
          if (num == 0 || num == 1) {
              return 1;
          }
          // dp[i]=dp[i-1]+dp[i-2],关键是需要大数取模
          int[] dp = new int[num + 1];
          dp[0] = 1;
          dp[1] = 1;
          dp[2] = 2;
          for (int i = 3; i <= num; i++) {
              dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
          }
          return dp[num];
      }
  }
  

  • 错误点1：边界问题,并且dp[0]=1

  0 赞同 0 条回复

  登录以回复
• 秋山丽奈 普通 2024年12月30日 下午8:13

  思路：递归+记忆化

  class Solution {
      HashMap<Integer, Integer> memo = new HashMap<>();
  
      public int trainWays(int num) {
          if(num <= 0){
              return 1;
          }
  
          if(num == 1){
              return 1;
          }
  
          if(this.memo.getOrDefault(num, -1) != -1){
              return this.memo.get(num);
          }
  
          int temp = (trainWays(num-1) + trainWays(num-2)) % 1000000007 ;
          this.memo.put(num, temp);
          return temp;
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 晓宇 普通 2024年12月28日 下午4:20

  class Solution {
  public:
      int trainWays(int num) {
          if(num <= 2){
              if(num <= 0) return 1;
              return num;
          }
          return trainWays(num - 1) + trainWays(num - 2);
  
      }
      //复杂度 o(2^n) o(n)
  };
  
  class Solution {
  public:
      int trainWays(int num){
          vector<int> arr(101,-1);
          return __trainWays(num,arr);
  
      }
  
      int __trainWays(int num,vector<int> &arr) {
          if(num <= 2){
              if(num <= 0) return 1;
              return num;
          }
          if(arr[num] != -1) return arr[num];
          int sum = (__trainWays(num - 1,arr) + __trainWays(num - 2,arr)) % 1000000007;
          arr[num] = sum;
          return sum;
  
      }
      // o(n) o(n)
  };
  

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月27日 下午4:03

  class Solution {
  public:
      int trainWays(int num) {
          int a = 1;
          int b = 2;
          if(num == 0) return 1;
          if(num <= 2) return num;
          for(int i = 2; i < num; i++) {
              int c = (a + b) % 1000000007;
              a = b;
              b = c;
          }
          return b;
      }
  };
  

  时间复杂度O(N)，空间复杂度O(1)。

  0 赞同 0 条回复

  登录以回复
• Xiang. 永久会员 2024年12月26日 下午12:01

  class Solution {
      public int trainWays(int num) {
          if(num<=1) return 1;
          if(num==2) return 2;
          int i=1;
          int j=2;
          int sum=0;
          for(int k=2;k<num;k++){
              sum=(i+j)%1000000007;
              i=j;
              j=sum;
          }
          return sum;
      }
  }
  时间复杂度：O（n）
  空间复杂度：O（1）
  

  0 赞同 0 条回复

  登录以回复