package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月15日 16:47
 * @description: 力扣70题 爬楼梯
 */
public class ClimbStairs {

 public static void main(String[] args) {
 Scanner sr = new Scanner(System.in);
 int n = sr.nextInt();
 System.out.println(new ClimbStairs_Solution().climbStairs1(n));
 System.out.println(new ClimbStairs_Solution().climbStairs2(n));
 }
}


class ClimbStairs_Solution{
 public int climbStairs1(int n){
 int []dp = new int[n+1];
 dp[0] = 1;
 for(int i = 1;i <= n;i++){
 dp[i] = dp[i-1];
 if(i > 1){
 dp[i] += dp[i-2];
 }
 }
 return dp[n];
 }
 public int climbStairs2(int n){
 int p = 0,q,r =1;
 for(int i =0;i < n;i++){
 q = p;
 p = r;
 r = 0;
 r += p;
 if(i == 0){
 continue;
 }
 r += q;
 }
 return r;
 }
}