遇到个动态规划问题，求大佬康康

别慌，DP先考虑状态再考虑转移就行。 首先考虑下如何表示状态。 显然的我们得表示出那些星星被销毁了那些没有。2^n的表示法自然是最简单的，但是肯定无法按时跑出来。因此我们得考虑简化一下。 由于只有相邻的星星才能合并，所以其实我们的状态只要能表达出哪些星星相邻即可。因此，我选择(i,j)来表示第i个星星和第j个星星之间的星星被消除掉了，以及f(i,j)是消除它们能得到的最大得分。 然后我们需要考虑如何转移，对于(i,j)，我们只需要知道最后被消除的a是谁就行。根据f(X,X)的定义，之前被消除可以获得最大分数就是f(i,a)+f(a,j)，至于具体怎么个消除顺序我不关心。而消除a的得分是与它相邻的两个星星乘积，即：S[i]*S[j]。故此，我们有： f(i,j)=for a max( f(i,a)+f(a,j)+S[i]*S[j]  ) 然后我们将伪代码转成C支持的格式 F[i][j]=for (int a=i+1;a<j;++a) F[i][j]=max(F[i][j],F[i][a]+F[a][j]+S[i]*S[j]) 最后只剩下两个星星，而且只能是首尾星星，所以结果即为F[0][n-1] 然后我们需要处理下空间复用以及遍历顺序的问题： 空间方面，由于F[a][j]同时被F[0..a][j]依赖，不是一次性的，不能压成一围 遍历顺序方面，由于F[i,a]、F[a,j]必须在F[i,j]之前计算，所以需要安排一下顺序，例如:For (j=n-1;j>=0;--j) for (i=0;i<j;++i); 最后需要处理下边界值以及初始值。略

区间dp，dp[i][j]表示消除范围(i, j)的最大得分，答案是dp[0][n-1]