题目难度：二星
考察点：动态规划

方法：动态规划

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]
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;
}