DP写程序的循环怎么开始:
看初始状态是是什么,再看状态转移方程是什么依赖顺序
比如LC375 初始状态 dp[i][i] = 0 转移方程dp[i][j] = min (i<=k<=j) { k + max(dp[i][k-1], dp[k+1][j]) }
那么明显是由初始状态看是从某一点向外扩展,由转移方程看是从低到高,所以循环为:
for (int i = 1; l < n; l++)
for (int i= 1;i <= n-l; i++) {
int j = i+l;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j; k++)
dp[i][j] = Math.min(dp[i][j], k + Math.max(dp[i][k - 1], dp[k + 1][j]));
}
return dp[1][n];
}
先(1,2)(2,3)。。。。(n,n+1) 再(1,3)(2,4)。。。。这样拓展