最小代价爬楼梯
最小代价爬楼梯
http://www.nowcoder.com/questionTerminal/355885694012495281f415387db22fde
题目难度：二星
考察点：动态规划
方法：动态规划
1.分析：
这个题的本质其实和跳楼梯差不多的，只不过加了代价而已，那么假设跳n个台阶的代价为f(n)那么：
如果第n个台阶是由跳1阶而来的，那么代价就是f(n-1)+a[n]
如果第n个台阶是由跳2阶而来的，那么代价就是f(n-2)+a[n]
由此可得：f(n) = min(f(n-1), f(n-2))+a[i]
当n=0时，f(0) = a[0]
当n=1时，f(1) = a[1]
如果第n个台阶是由跳1阶而来的，那么代价就是f(n-1)+a[n]
如果第n个台阶是由跳2阶而来的，那么代价就是f(n-2)+a[n]
由此可得：f(n) = min(f(n-1), f(n-2))+a[i]
当n=0时，f(0) = a[0]
当n=1时，f(1) = a[1]
tips：
(1). 这个题的题意不是很明确，其实根据数据测出是应该跳出n阶，即计算的是dp[n+1]。
(2). 输入还是以字符串输入的比较恶心，还是按照之前的方法使用stringstream处理，也很方便的。
(1). 输入一个字符串，然后根据stringstream处理，得到一个长度为n的整型数组。
(2). 定义dp数组，其中dp[i]表示跳到第i个台阶的最小代价，初始化dp的值，即dp[0] = a[0], dp[1] = a[1];
(3). 按照之前的状态转移方程进行遍历计算。
(4). 输出dp[n]即可，因为下标是从0开始的。
2.复杂度分析：
时间复杂度：O(n)空间复杂度：O(n)
3.代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;
int a[MAXN], dp[MAXN];
int main() {
string s; cin>>s;
stringstream ss(s);
int n = 0, x;
ss>>a[n++];
char ch;
while(ss>>ch>>a[n]) n++;
dp[0] = a[0], dp[1] = a[1];
for(int i=2; i<=n; i++) {
dp[i] = min(dp[i-1], dp[i-2])+a[i];
}
cout<<dp[n]<<endl;
return 0;
}
巨人网络公司福利 65人发布
