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

共以下 8 个回答

• June 普通 2023年11月23日 下午4:35

  class Solution {
      public int trainWays(int num) {
          int mod = 1000000007;
          if(num <= 1)
              return 1;
          int num1 = 1,num2 = 1,num3 = 2;
  
          for(int i=2;i<=num;i++)
          {
              num3 = num1 + num2;
              num3 %= mod; //求余
              num1 = num2;
              num2 = num3;
          }
          return num3;
      }
  
  }
  

  0 赞同 0 条回复

  登录以回复
• 桎梏 普通 2023年9月16日 下午3:33

  //斐波那契
  class Solution {
      public int numWays(int n) {
          int a = 1, b = 1;
          int sum;
          for(int i=0; i<n; i++) {
              sum = (a+b) % 1000000007;
              a = b;
              b = sum;
          }
          return a;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Marshan 普通 2023年9月10日 下午4:52

  比较简单

  class Solution {
  public:
      int numWays(int n) {
          if(n < 2){
              return 1;
          }
          // vector<int> dp(n+1,0);
          int dp1 = 1,dp2 = 1;
          for(int i = 2;i <= n;++i){
              int tmp = (dp1 + dp2) % 1000000007;
              dp2 = dp1;
              dp1 = tmp;
          }
  
          return dp1;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• Mby 普通 2023年8月22日 下午1:26

  class Solution {
      public int numWays(int n) {
          int a = 1, b = 1, sum;
          //递归公式 f(n) = f(n - 1) + f(n - 2);
          for(int i = 0; i <n; i++){
              sum = (a + b) %1000000007;
              a = b;
              b = sum;
          }
          return a;
      }
  }
  
  

  0 赞同 0 条回复

  登录以回复
• 阿尚 普通 2023年8月12日 下午8:05

  class Solution {
      public int numWays(int n) {
          if(n < 2) return 1;
          //dp：跳到第i级台阶有dp[i]种方法
          int[] dp = new int[n + 1];
          dp[0] = 1;
          dp[1] = 1;
  
          for(int i = 2; i <= n; i++){
              dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
          }
  
          return dp[n];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 长河呼叫黄江 普通 2023年8月12日 下午3:25

  8.10 周四
  Day31：下面是代码

  class Solution {
      public int numWays(int n) {
          int a = 1, b = 1, sum;
          for(int i = 0; i < n; i++){
              sum = (a + b) % 1000000007;
              a = b;
              b = sum;
          }
          return a;
      }
  }
  
  

  0 赞同 0 条回复

  登录以回复
• AD钙奶 普通 2023年8月11日 上午11:44

  本质上也是斐波那契，但注意这里要把取模放在循环里面

  class Solution {
      public int numWays(int n) {
          if(n <= 1) return 1;
          if(n == 2) return 2;
          int[] dp = new int[n + 1];
          dp[1] = 1;
          dp[2] = 2;
          for(int i = 3; i <= n; i ++) {
              dp[i] += (dp[i-1] + dp[i-2]) % 1000000007;
          }
          return dp[n];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• NullPointerException 普通 2023年8月10日 下午8:40

  class Solution {简单题
  public int numWays(int n) {
  int dp[]=new int[n+1];
  if(n<=1) return 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];
  dp[i]=dp[i]%1000000007;
  }
  return dp[n];
  }
  }

  0 赞同 0 条回复

  登录以回复