c - 在一次采访中问:动态编程

Closed. This question needs details or clarity。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？添加详细信息并通过editing this post阐明问题。
                        
                        6年前关闭。
                                                                                            
                
        
“ 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 1 4 1 1 1 1 1 8 1 1 1 1

输出量

2

9 8

最佳答案

让：

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
...

关于c - 在一次采访中问:动态编程，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20021540/