AC代码(C++): 简单的一维dp,可以用递推的方式或记忆化搜索的方式。 本题本质是求fibonacci数列的第n项:
class Solution {
public:
int climbStairs(int n) {
int dp[n+1];
dp[0]=dp[1]=1;
for(int i=2; i<=n; ++i)
dp[i] = dp[i-1]+dp[i-2];
return dp[n];
}
};