C++ 编程挑战：气球游戏 - 寻找最少扎破气球数

众所周知，ty奥信队的同学们早已回归校园，积极地备赛CSP - J/S，他们的暑假比别的同学少一大半，但是在每位同学身上都可以看到自信和快乐的光芒! 这是因为每天老师都会组织同学们进行体育锻炼，并且给同学们玩一些有趣的体育游戏，今天的游戏是这样的:

体育老师拿出n个气球从左到右排成一排，每个气球上面都会有一个数字编号a;。你可以选择扎破某一些气球，但是最多只能扎破n - 1个气球，至少要剩下一个气球留在场上。假设目前你已经扎破了一些气球，场上还剩下m个气球，那么胜利的规则是这m个气球中的每一个气球i(1 < i< m)，如果气球上的数字a;恰好等于i，那么你将赢得游戏的胜利!

由于你的体力有限，所以你需要找到最小的扎破气球的数目，使得你能获得游戏的胜利，并把这个最小的数目输出出出来；而如果无论怎么扎破气球都没办法赢得胜利，那么输出-1.

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> balloons(n);
    for (int i = 0; i < n; i++) {
        cin >> balloons[i];
    }
    
    vector<int> dp(n, 1);
    int maxBalloons = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (balloons[i] == dp[j] + 1) {
                dp[i] = max(dp[i], dp[j] + 1);
                maxBalloons = max(maxBalloons, dp[i]);
            }
        }
    }
    
    cout << n - maxBalloons << endl;
    
    return 0;
}

解题思路

这道题目可以使用动态规划来解决。我们用dp[i]来表示以第i个气球结尾的最长连续序列长度。

首先，我们初始化dp[0]为1，因为单个气球可以构成一个长度为1的序列。

然后，我们遍历所有气球，对于每个气球i，我们遍历之前的气球j(j < i)，如果当前气球i上的数字等于dp[j] + 1，则更新dp[i]为dp[j] + 1，同时更新maxBalloons为dp[i]。

最后，我们输出n - maxBalloons，即最少需要扎破的气球数。

总结

这道题目是一道经典的动态规划问题，可以帮助我们理解动态规划的思想和应用。通过这道题目，我们可以学习如何使用动态规划来解决最优化问题。