c - 采访中询问: Dynamic Programming

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 9 年前。

Improve this question

“N”枚炸弹排成一排。每颗炸弹都有一个与之对应的“索引”。假设第 i 个位置炸弹的索引为 k。意思是当第i颗炸弹扩散时，它与其左边的k颗炸弹一起扩散，右边的k颗炸弹也一起扩散。输入的第一行包含数字 N(炸弹数量)，下一行包含空格分隔的炸弹索引(k)。将输出打印为此类炸弹的最小数量，该炸弹在扩散时会扩散所有其他炸弹，后跟炸弹索引。如果有多个这样的索引组合，请将它们打印在单独的行上。

例如

输入:

8

1 2 7 3 4 9 3 4

输出

1

9

输入:

20

1 1 1 9 1 1 1 1 1 4 1 1 1 1 1 8 1 1 1 1

输出

2

9 8

Answer 1

让:

dp[i] = minimum number of bombs that need to be defused in order to defuse
        all bombs in [1, i] considering only bombs in [1, i]

我们有:

dp[anything<=0] = 0
dp[1] = 1 <- must defuse the first bomb
dp[k] = min{dp[k - a[k]] + overlap, <- if the current bomb also defuses
                                       a[k] to its left and right, then we can just 
                                       defuse that and reduce the problem 
                                       to defusing bombs [1, k - a[k]]
            dp[k - a[k] + 1] + overlap, <- same reasoning; some overlaps might provide
                                           a better solution
            dp[k - a[k] + 2] + overlap,
            ...
            dp[k - 1] + overlap}

哪里overlap是 1如果炸弹位于p = k - a[k] + i也不能化解k第一枚炸弹和0否则。

答案是dp[n] 。直接实现是O(n^2) 。也许可以使其呈线性。

工作示例:

a = 1 2 7 3 4 9 3 4
dp[1] = 1
dp[2] = min{dp[2 - 2] + 1,
            dp[2 - 1] + 0 (because the first bomb also defuses this one}
      = 1
dp[3] = min{dp[3 - 7] + 1,
            dp[3 - 2] + 1 (because the first bomb does not also defuse this one),
            dp[3 - 1] + 0}
      = 1
...