好吧， 也别着急，动态规划本来就是很难理解的， 你们也做了一些动态规划的提了。 也了解DP本来就很难想， 我开始做的时候也很慢， 也是自己理解了好久， 开始都这样。 我讲的也有点快， 那块没理解， 欢迎随时来问。 我那讲的不好理解， 就指出来， 我改进。大家相互学习。
DP一般最难想的就是状态转移方程。
区间型DP一般（也有例外）都是从小的区间开始求最优解，然后不断扩大所求的区间，而求大区间时所用到的小区间前面已经求过了。so直接用就行啦。
区间内枚举最后一次的位置， 所以说区间动规一般都是三层for循环， 前两层用来控制区间长度， 最后一层用来枚举最后一次的位置， 还有需要注意的是区间用从小到大， 因为动态规划就是后面的用到前面的出的结果递推后面的结果。 dp[i][j] 表示从第 i 堆合并到第 j 堆的最小代价，
sum[i][j] 表示第 i 堆到第 j 堆的石子总和，则动态转移方程：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]) (i <= k <= j - 1)。
//关键的一块：：合并i到j的所有石子。那前一状态一定是两堆石子。
//这步我们就枚举所有可能的位置（两堆石子分开的位置）
for(int k = i; k < j; k++)
{
if(dp[i][j] > dp[i][k] + dp[k+1][j] + sum[i][j])
dp[i][j] = dp[i][k] + dp[k+1][j] + sum[i][j];
}
额。。举个例子吧：4个数（1,2,3, 4）
某区间（i到j）相距为1时 d = 1 可求出f[1][2] = 3; f[2][3] = 5; f[3][4] = 7;
d = 2时 , f[1][3] = min(f[1][2] + f[3][3], f[1][1] + f[2][3])+sum[1][3]= 9; (这里f[3][3] = 0,应为合并自己没花费)。同理f[2][4] = 14；
d = 3时：f[1][4] = 19;
枚举前一状态 f[1][4] = min(f[1][1]+f[2][4], f[1][2]+f[3][4], f[1][3] + f[4][4]) + sum[1][4];到这有点眉目没。
耐心点看看！！
还有一点需要注意， 他的最后结果是用的总代价， 所以dp的结果要来自合并当前这次的代价和 当前这次以前的总代价。
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int N = 220;
const int M = 10e9;
int n, s[N][N], a[N], f[N][N];
int main()
{
while(scanf("%d", &n) != EOF)
{
memset(s, 0, sizeof(s));
memset(a, 0, sizeof(a));
memset(f, 0, sizeof(f));
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j++)
{
f[i][j] = M;
for(int k = i; k <= j; k++)
s[i][j] = s[i][j] + a[k];
}
}
for(int i = 1; i <= n; i++)
f[i][i] = 0;
for(int i = 1; i < n; i++)
{
for(int j = 1; j <= n-i; j++)
{
for(int k = j; k <= i + j - 1; k++)
{
if(f[j][i+j] > f[j][k] + f[k+1][i+j]+s[j][i+j])
f[j][i+j] = f[j][k] + f[k+1][i+j]+s[j][i+j];
}
printf("f[%d][%d] = %d
", j, i+j, f[j][i+j]);
}
}
printf("%d
", f[1][n]);
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
递归方法
using namespace std;
const int N = 220;
const int M = 10e9;
int n, s[N][N], a[N], d[N][N];
void sum()
{
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j++)
{
for(int k = i; k <= j; k++)
s[i][j] += a[k];
// printf("s[%d][%d] = %d
", i, j, s[i][j]);
}
}
}
int dp(int x, int y)
{
if(d[x][y] != 10e8) return d[x][y];
for(int i = x; i < y; i++)
d[x][y] = min(d[x][y], dp(x, i) + dp(i+1, y) + s[x][y]) ;
// printf("d[%d][%d] = %d
", x, y, d[x][y]);
return d[x][y];
}
int main()
{
while(scanf("%d", &n) != EOF)
{
memset(s, 0, sizeof(s));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
d[i][j] = 10e8;
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sum();
for(int i = 1; i <= n; i++)
d[i][i] = 0;
int ans = dp(1, n);
printf("%d
", ans);
}
return 0;
}
分类：