• 动态规划dp
  • 状态压缩，只保留前两个状态
    import java.util.Scanner;
public class Main {
  public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      if(n <= 2){
          System.out.println(n);
      }else{
          //            int[] dp = new int[n + 1];
          //            dp[1] = 1;
          //            for(int i = 2; i < dp.length; i++){
          //                dp[i] = dp[i - 1] + dp[i - 2];
          //            }
          //            System.out.println(dp[dp.length-1]);
          int f2 = 1;
          int f1 = 1;
          int f = 2;
          for(int i = 2; i <= n; i++){
              f = f1 + f2;
              f2 = f1;
              f1 = f;
          }
          System.out.println(f);
      }
  }
}