>我在topcoder上做了一个问题，遇到了一个DP问题（http://goo.gl/hjeaS）
这应该有一个有效的 dp 解决方案，但我被卡住了。我用了一个数组 res[i][j][k] 来存储子问题，但我无法弄清楚执行，尤其是更精细的细节。
r[i][j][k] 将存储要在 i 和 j 之间插入的加号的最小编号，以获得 k 的总和。因此，我循环了i，j和k，在i和j之间的每个位置插入了一个加号。最小值将在遍历所有元素 i 到 j（对于特定总和 k）后获得。不过，我不确定数组的初始值以及限制应该是多少。有没有更有效的解决方案？（我的似乎是O（n³k））
附言我知道还有另一个类似的问题，但没有一个答案真正解释了该问题的 dp 解决方案背后的逻辑/代码。
我认为 2D 数组足以解决这个问题，因为您需要插入的只是一个加号，没有括号或优先级，所以只需使用 res[i][j] 来记录数据。
设 res[i][j] 表示要为前 i 个字符插入加号的最小编号，以获得总和 j。 因此，整个时间复杂度将为 O（n^2*k）