悟云

动态规划

引言

Those who cannot remember the past are condemned to repeat it.
动态规划算法的核心是记住已经求过的解,记住求解的方式有两种:自顶向下的备忘录法和自底向上。

小试牛刀-杠条切割问题


上图节选自算法导论。

经典朴素递归

1
2
3
4
5
6
7
8
9
10
11
12
13
int CutRod(const int *rodLen2Price, int curRodLen) {
if (curRodLen == 0) {
return 0;
}
int q = -1;
for (int i = 1; i <=curRodLen; ++curRodLen) {
int tmp = rodLen2Price[i] + CutRod(rodLen2Price, curRodLen-i);
q = q < tmp ? tmp : q;
}
return q;
}

自顶向下递归实现的CutRod效率很差,原因在于CutRod反复地用相同的参数值对自身进行递归调用,即它反复求解相同的子问题。而且由于递归调用次数太多会栈溢出。

动态规划-自顶向下

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
int MemorizedCutRodAux(const int *rodLen2Price, int curRodLen, int *optimalRodTotalMoney) {
cout << "调用MemorizedCutRodAux"<< endl;
if (optimalRodTotalMoney[curRodLen] >= 0) {
return optimalRodTotalMoney[curRodLen];
}
int q = -1;
if (curRodLen == 0) {
q = 0;
} else {
for (int i = 1; i <=curRodLen ; ++i) {
int tmp = rodLen2Price[i] + MemorizedCutRodAux(rodLen2Price, curRodLen-i, optimalRodTotalMoney);
q = (q < tmp ? tmp : q);
}
}
optimalRodTotalMoney[curRodLen] = q;
return q;
}
int MemorizedCutRod(const int *rodLen2Price, int curRodLen) {
int * optimalRodTotalMoney = new int[curRodLen + 1];
for (int i = 0; i <= curRodLen; ++i) {
optimalRodTotalMoney[i] = -1;
}
return MemorizedCutRodAux(rodLen2Price, curRodLen, optimalRodTotalMoney);
}

此方法仍按自然的递归形式编写过程,但过程会保存每个子问题的解。当需要一个子问题的解时,过程首先检查是否已经保存过此解。如果是,则直接返回保存的值,从而节省了计算时间;否则,按通常方式计算这个子问题。

动态规划-自底向上

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
void BUCutRod(const int *rodLen2Price, int curRodLen, int * optimalRodTotalMoney, int *optimalSolution) {
optimalRodTotalMoney[0] = 0;
for (int i = 1; i <=curRodLen; ++i) {
int q = -1;
for(int j = 1; j <= i; ++j) {
int tmp = rodLen2Price[j] + optimalRodTotalMoney[i-j];
if (q < tmp) {
q = tmp;
optimalSolution[i] = j;
}
}
optimalRodTotalMoney[i] = q;
}
}
void PrintBUCutRod(const int *rodLen2Price, int curRodLen, int * optimalRodTotalMoney, int *optimalSolution) {
BUCutRod(rodLen2Price, curRodLen, optimalRodTotalMoney, optimalSolution);
cout << "长度为" << curRodLen << "的杠条最大收益为:" << optimalRodTotalMoney[curRodLen] << endl;
cout << "最优方案的杠条长度分别为:";
while (curRodLen != 0) {
cout << optimalSolution[curRodLen] << " ";
curRodLen -= optimalSolution[curRodLen];
}
cout << endl;
}

恰当定义子问题“规模”的概念,使得任何子问题的求解都只依赖于“更小的”子问题的求解。因此,我们可以将子问题按照规模顺序,由小至大顺序进行求解。当求解某个子问题时,它所依赖的那些更小的子问题都已求解完毕,结果已经保存。每个子问题只需求解一次,当我们求解它时,它的所有前提子问题都已求解完成。
由于没有频繁的递归函数调用的开销,自底向上方法的时间复杂度函数通常具有更小的系数。