algorithm - 射气球并收集最高分

Question

有 10 个气球，每个气球上都写有一些点。如果顾客射气球，他将得到的分数等于左气球上的分数乘以右气球上的分数。客户必须收集最高分才能赢得这场比赛。最高分是多少？他应该按什么顺序射气球才能获得最高分？

请注意，如果只有一个气球，那么您将返回那个气球上的点数。

我正在尝试检查所有 10 个!排列以找出最大点。有没有其他方法可以有效地解决这个问题？

Answer 1

正如我在评论中所说，使用位掩码的动态编程解决方案是可能的，我们可以做的是在 1 的位置保留一个位掩码。在 bit索引于 i意味着 ith气球被击中，一个0告诉它还没有被 Gunicorn 。

因此只需要掩码的动态规划状态，在每个状态下，我们可以通过遍历所有尚未射出的气球并尝试射出它们以找到最大值来过渡到下一个状态。

这种解决方案的时间复杂度为:O((2^n) * n * n)空间复杂度为 O(2^n) .

C++ 代码，未调试，您可能需要调试它:

int n = 10, val[10], dp[1024];    //set all the values of dp table to -1 initially

int solve(int mask){
    if(__builtin_popcount(mask) == n){
        return 0;
    }
    if(dp[mask] != -1) return dp[mask];

    int prev = 1, ans = 0;
    for(int i = 0;i < n;i++){
        if(((mask >> i) & 1) == 0){ //bit is not set
            //try to shoot current baloon
            int newMask = mask | (1 << i);
            int fwd = 1;
            for(int j = i+1;j < n;j++){
                if(((mask >> j) & 1) == 0){
                    fwd = val[j];
                    break;
                }
            }
            ans = max(ans, solve(newMask) + (prev * fwd));
            prev = val[i];
        }
    }
    return dp[mask] = ans;
}