70.Climbing Stairs

1.Description(Easy)

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example

Given an example n=3 , 1+1+1=2+1=1+2=3

return 3.

2.Code

(高频)统计方案个数+一维坐标

state: f(n) 表示爬了n 步后有几种爬法。-->开int[n+1] 返回f(n)

function:f(n)=f(n-1)+f(n-2);

Initialize: f(0)=1, f(1)=1;

Answer: f(n)

 public int climbStairs(int n) {

      if(n<=1){
            return 1;
        }

        //state:number from 0 to n
        int[] path=new int[n+1];

        //Initialization:
        path[0]=1;
        path[1]=1;

        //function:
        for(int i=2;i<=n;i++){
            path[i]=path[i-1]+path[i-2];
        }

        //answer:
        return path[n];
    }