区间dp（自用）

基本原理

与所有dp一样，这是一种有顺序的、记忆化的、更聪明的暴力搜索。基本思路是将大区间拆分成小区间，记忆化储存小区间的值（dfs或for循环），再利用转移公式得到大区间的值。

流程

一般有两种实现方式：记忆化搜索，dp遍历

double dfs(int k,int x1,int y1,int x2,int y2) {
if (f[k][x1][y1][x2][y2] >= 0) return f[k][x1][y1][x2][y2];
if (k == n) {
return f[k][x1][y1][x2][y2] = get(x1, y1, x2, y2);
}
double t = 1e9;
for (int i = x1; i < x2; i) {
t = min(t, dfs(k + 1, x1, y1, i, y2) + get(i+1, y1, x2, y2));
t = min(t, dfs(k + 1, i + 1, y1, x2, y2) + get(x1, y1, i, y2));
}
for (int i = y1; i < y2; i) {
t = min(t, dfs(k + 1, x1, y1, x2, i) + get(x1, i+1, x2, y2));
t = min(t, dfs(k + 1, x1, i + 1, x2, y2) + get(x1, y1, x2, i));
}
return f[k][x1][y1][x2][y2] = t;
}

for (int len = 1; len <= n; len) {
for (int i = 1; i+len-1<=n; i) {
int j = i + len - 1;
if (i == j) {
f[i][j] = a[i];
g[i][j] = i;
}
else {
int left, right;
for (int k = i; k < j; k) {
if (k == i)left = 1;
else left = f[i][k-1];
if (k == j)right = 1;
else right = f[k + 1][j];
if (f[i][j] < left * right + a[k]) {
f[i][j] = left * right + a[k];
g[i][j] = k;
}
}
}
}
}

注意细节

明确每一维的实际意义；
注意观察题目n的取值范围，若比较小则有可能为区间dp（因为该算法复杂度一般要O(n3)）