基本思想
将待求解的问题分解成若干子问题，先求子问题，然后从子问题的解得到原问题的解。适用于动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。保存已解决子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
步骤
找出最优解的性质，并刻画其结构特征递归地定义最优值以自底向上地方式计算最优值根据计算最优值时得到地信息，构造最优解
例题
矩阵连乘问题
#include<iostream>
using namespace std
;
int p
[7] = {30, 35, 15, 5, 10, 20, 25};
int m
[6][6];
int s
[6][6];
void MatrixChain(int *p
, int n
, int m
[6][6], int s
[6][6])
{
for(int i
=1; i
<=n
; i
++) m
[i
][i
] = 0;
for(int r
=2; r
<=n
; r
++){
for(int i
=1; i
<=n
-r
+1; i
++){
int j
= i
+r
-1;
m
[i
][j
] = m
[i
+1][j
] + p
[i
-1]*p
[i
]*p
[j
];
s
[i
][j
] = i
;
for(int k
=i
+1; k
<j
; k
++){
int t
= m
[i
][k
] + m
[k
+1][j
] + p
[i
-1]*p
[k
]*p
[j
];
if(t
< m
[i
][j
]){
m
[i
][j
] = t
;
s
[i
][j
] = k
;
}
}
}
}
}
void Traceback(int i
, int j
, int s
[6][6])
{
if(i
== j
) return ;
Traceback(i
, s
[i
][j
], s
);
Traceback(s
[i
][j
]+1, j
, s
);
cout
<< "MultipyA" << i
<< "," << s
[i
][j
];
cout
<< "and A" << s
[i
][j
]+1 << "," << j
<< endl
;
}
int main()
{
MatrixChain(p
, 6, m
, s
);
Traceback(2, 5, s
);
return 0;
}
最长公共子序列
#include<iostream>
using namespace std
;
char x
[] = "asdfghjk", y
[] = "dfgrtufss";
int c
[100][100];
int b
[100][100];
void LCSLength(int m
, int n
, char *x
, char *y
, int c
[][100], int b
[][100])
{
for(int i
=1; i
<=m
; i
++) c
[i
][0] = 0;
for(int i
=1; i
<=n
; i
++) c
[0][i
] = 0;
for(int i
=1; i
<=m
; i
++) {
for(int j
=1; j
<=n
; j
++){
if(x
[i
] == y
[j
]){
c
[i
][j
] = c
[i
-1][j
-1] + 1;
b
[i
][j
] = 1;
}
else if(c
[i
-1][j
] >= c
[i
][j
-1]){
c
[i
][j
] = c
[i
-1][j
];
b
[i
][j
] = 2;
}
else{
c
[i
][j
] = c
[i
][j
-1];
b
[i
][j
] = 3;
}
}
}
}
void LCS(int i
, int j
, char *x
, int b
[][100])
{
if(i
==0 || j
==0) return;
if(b
[i
][j
] == 1){
LCS(i
-1, j
-1, x
, b
);
cout
<< x
[i
];
}
else if(b
[i
][j
] == 2) LCS(i
-1, j
, x
, b
);
else LCS(i
, j
-1, x
, b
);
}
int main()
{
LCSLength(8, 9, x
, y
, c
, b
);
LCS(8, 9, x
, b
);
return 0;
}
