程序员人生网站导航

LeetCode Climbing Stairs

栏目：互联网时间：2014-12-07 09:38:42

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?

思路分析：考察DP，定义ClimbWays数组，ClimbWays[n]表示n steps不同的走法，如果第n步是1个单步，这类情况的走法有ClimbWays[n⑴]种；如果第n步是1个双步，这类情况的走法有ClimbWays[n⑵]种；因此可以得到DP方程ClimbWays[n]=ClimbWays[n⑴] + ClimbWays[n⑵] .

public class Solution { public int climbStairs(int n) { //04:10 int [] climbWays = new int[n+1]; if(n == 0) return 0; if(n == 1) return 1; climbWays[1] = 1; climbWays[2] = 2; for(int i = 3; i <= n; i++){ climbWays[i] = climbWays[i⑴] + climbWays[i⑵]; } return climbWays[n]; } //04:14 }

------分隔线----------------------------

上一篇 牛腩之CSS简介

下一篇 centos6.5配置samba

------分隔线----------------------------