动态规划

Posted on In

引言

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;
}

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