爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

动态规划：
状态转移方程：res[n] = res[n-1] + res[n-2]
解释：当前台阶数下，最后一步可以上2阶或1阶，总数即为两种情况之和。要看最后一步的走法

Java版本：

class Solution {
    public int climbStairs(int n) {
        if(n == 1)
            return 1;
        int[] res = new int[n+1];
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        for(int i = 3;i<n+1;i++){
            res[i] = res[i-1] + res[i-2];
        }
        return res[n];
    }
} 

Go语言版本：

package climbing_stairs

//动态规划：当前台阶数下，最后一步可以上2阶或1阶，总数即为两种情况之和。
func climbStairs(n int) int {
    if n < 2 {
        return 1
    }
    rec := make([]int,n+1)
    rec[0],rec[1] = 1,1
    for i := 2; i <= n ; i++{
        rec[i] = rec[i-1] + rec[i-2]
    }
    return rec[n]
}


package climbing_stairs

import (
    "fmt"
    "github.com/stretchr/testify/assert"
    "testing"
)

type ans struct {
    one int
}

type para struct {
    n int
}

type question struct {
    para
    ans
}

func Test_climbStairs(t *testing.T) {
    ast := assert.New(t)

    qs := []question{

        question{
            para{
                0,
            },
            ans{
                1,
            },
        },

        question{
            para{
                10,
            },
            ans{
                89,
            },
        },

        question{
            para{
                44,
            },
            ans{
                1134903170,
            },
        },

        question{
            para{
                1,
            },
            ans{
                1,
            },
        },
    }

    for _, q := range qs {
        a, p := q.ans, q.para
        fmt.Printf("~~%v~~", p)
        ast.Equal(a.one, climbStairs(p.n), "输入:%v", p)
    }
}