题解 | 最小花费爬楼梯

#include <iostream>
#include <vector>

using namespace std;

int main() 
{
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];

    // 创建 dp 表
    vector<int> dp(n);

    // 初始化 dp 表
    dp[0] = nums[0];
    if(n == 1) 
    {
        cout << dp[0] << endl;
        return 0;
    }
    dp[1] = nums[1];

    // 填表
    for(int i = 2; i < n; i++)
        dp[i] = nums[i] + min(dp[i -1], dp[i - 2]);

    // 返回
    cout << min(dp[n - 1], dp[n - 2]) << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

dp表分析 : 常用思维, dp[i] 走到第 i 个楼梯需要的最少步数

状态转移方程 : 第 i 个位置可以从 i - 1 或者 i - 2 开始走, 那么就是 dp[i] = min(dp[i -1], dp[i -2]) + nums[i] , 也就是前面的最少加上当前需要走的楼梯

初始化 : 第一个楼梯就是本身楼梯数, 因为你可以直接到第一个楼梯走, 第二个楼梯同理

返回值 : 我们只需要比较 min(dp[n - 1], dp[n - 2]) 即可!