题目一
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解法一：动态规划
将dp[i]数组定义为到达第i阶楼梯有多少种方法，由每次可以爬1或2阶可以得到递推公式：
d
p
[
i
]
=
d
p
[
i
−
1
]
+
d
p
[
i
−
2
]
dp[i]=dp[i-1]+dp[i-2]
d
p
[
i
]
=
d
p
[
i
−
1
]
+
d
p
[
i
−
2
]
其中，dp[i-1]、dp[i-2]分别为到达第i-1、i-2阶楼梯有多少种方法。然后再确定边界条件，dp[1]=1,dp[2]=2。这样得出来的实现过程时间复杂度和空间复杂度都是o(n),可以利用滚动数组的思想将空间复杂度降为常数，如下面代码：
class Solution {
public:
int climbStairs(int n) {
if(n<=2)
return n;
int dp1=1,dp2=2,dp3;
for(int i=3;i<=n;++i)
{
dp3=dp1+dp2;
dp1=dp2;
dp2=dp3;
}
return dp3;
}
};
题目二
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
解法：
此题的dp[i]数组可以定义为到达第i阶楼梯的最低花费，递推公式为：
d
p
[
i
]
=
m
i
n
(
d
p
[
i
−
1
]
+
c
o
s
t
[
i
−
1
]
,
d
p
[
i
−
2
]
+
c
o
s
t
[
i
−
2
]
)
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
d
p
[
i
]
=
m
i
n
(
d
p
[
i
−
1
]
+
c
o
s
t
[
i
−
1
]
,
d
p
[
i
−
2
]
+
c
o
s
t
[
i
−
2
]
)
确定边界条件：
dp[0]=0,dp[1]=0
同样利用滚动数组的思想降低空间复杂度，代码如下：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int p=0,q=0,r;
for(int i=2;i<=cost.size();++i)
{
r=min(q+cost[i-1],p+cost[i-2]);
p=q;
q=r;
}
return r;
}
};