我试图解决这个问题 - http://www.spoj.pl/problems/LISA/
我最初想到了 Greedy，但后来意识到它行不通。这似乎是一个DP问题。我无法形成递归关系。我无法形成递归关系。不只是这个问题，每当我遇到一个稍微困难的DP问题时，我都会卡住。我知道这一定很常见，实践会有所帮助。但我只是从一个问题转移到另一个问题而没有真正找到解决方案。
对于上述问题和一般情况下，DP 遇到的任何建议都会很棒。
非常感谢。
问问题
1204 次
3 回答
5
请注意，允许的操作只有+和*- 关于两个操作数严格递增的二元操作（它们是正数）。
令dp[l][r]为子串 [l,r] 的最大结果
以下是有关此问题的提示，也适用于每个 dp。
1) 什么是基本情况？（提示：非常简单的东西，不会通过添加/删除括号来改变它的值）
2) 你如何从大问题转移到小问题？（提示：您可以尝试找到上次操作的位置）
于 2012-06-23T07:54:11.777 回答
0
解决这个问题只需要一个简单的矩阵链乘法实现。
于 2013-10-17T22:16:48.497 回答
0
- 将有 n/2+1 个数字
- n/2 符号
- 为每个符号分配剩下的数字。
- 创建一个方阵用相应的数字初始化对角线，现在 i,j=max((i,k)(sign right of kth number)(k+1,j)) i<=k
- (0,m-1) 将是答案
- 请注意，它将流向（0，m-1），因此是 DAG（有向无环图）。
- 拇指规则：如果问题的任何图形表示可以优化为 DAG，则可以通过 DP 解决
有关解决方案，请参阅： https ://shashankmishracoder.wordpress.com/2019/03/29/spoj-lisa-matrix-chain-multiplication-variation/
于 2019-03-29T16:15:55.777 回答