【杂题】剑指 Offer 10- I. 斐波那契数列

共以下 6 个回答

• Marshan 普通 2023年9月10日 下午4:44

  注意大数处理

  class Solution {
  public:
      int fib(int n) {
          vector<long long> dp(n+1,0);
          if(n < 2){
              return n;
          }
          dp[0] = 0;
          dp[1] = 1;
          for(int i = 2;i <= n;++i){
              dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
          }
  
          return dp[n];
      }
  };
  

  0 赞同 0 条回复

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

  class Solution {
      public int fib(int n) {
          int a  = 0, b = 1, sum;
          for(int i = 0; i < n; i++){
              sum = (a+b) %1000000007;
               // a 原本指向的值不会在用到，所以让 a 保存 b，b 保存 sum，之后重新计算 sum，如此循环
              a = b;
              b = sum;
          }
          return a;
      }
  }
  
  

  0 赞同 0 条回复

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

  class Solution {
      public int fib(int n) {
          if(n == 0) return 0;
          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]) % 1000000007;//取模
          }
  
          return dp[n];
      }
  }
  

  0 赞同 0 条回复

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

  8.10 周四
  Day31：下面是代码

  class Solution {
      public int fib(int n) {
          int a = 0, 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:43

  很经典的题了

  class Solution {
      public int fib(int n) {
          if(n == 0) return 0;
          if(n <= 2) return 1;
          int a = 1, b = 1;
          int res = 0;
          for(int i = 3; i <= n; i ++) {
              res = (a + b) % 1000000007;
              a = b;
              b = res;
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• NullPointerException 普通 2023年8月11日 上午10:54

  class Solution {打卡
  public int fib(int n) {
  int dp[]=new int [n+1];
  if(n0) return 0;
  dp[0]=0;
  if(n1) return 1;
  dp[1]=1;
  for(int i=2;i<=n;i++)
  {
  dp[i]=dp[i-1]+dp[i-2];
  dp[i]=dp[i]%1000000007;
  }
  return dp[n];
  }
  }

  0 赞同 0 条回复

  登录以回复