<一>什么是动态规划?

动态规划是解决多阶段决策问题常用的最优化理论。动态规划适合求解多阶段决策问题的最优解,也可用于含有线性或非线性递推关系的最优解,但是这些问题都必须满足最优化原理子问题的“无后效性”

<二>最优化原理:

“最优化原理是指一个最优策略的子策略,对于它的初态和终态而言也必是最优的。”–百度百科。

对于一个问题的最优子结构,不管之前的状态和过去的决策是怎样的,对之前的决策所形成的现在的状态来说,其后的决策必须是最优策略。换而言之,不管前面的决策如何,从现在起所用的决策,必须是在之前的决策下所形成的状态的基础上的最优决策。这样形成的最优子结构就符合最优化原理。

<三>无后效性:

“某阶段的状态一旦确定,则此后过程的演变不再受此前各种状态及决策的影响。

简单的说,就是当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响过程未来的演变,“未来与过去无关”。

具体地说,如果一个问题被划分各个阶段之后,阶段I中的状态只能由阶段i-1中(或多个有限历史阶段)的状态通过状态转移方程得来,与其它状态没有关系,特别是与未发生的状态没有关系。”–百度百科

无后效性这个概念对于初学者而言的确是有点难以理解,很容易陷入一种思维误区。需要自己去多多思考。

<四>动态规划的基本思想:

    对子问题进行分解,通过求解小规模的子问题再反推出原问题的解。动态规划沿着决策的阶段划分子问题,决策的阶段可以随时间划分 ,也可以随问题的演化状态去划分。
    动态规划并没有固定的解题模式,而是作为一种解题的指导思想存在。使用动态规划解题时一般需要四个步骤:
    -定义最优子问题
    -定义状态
    -定义决策和状态转移方程
    -确定边界条件

1、定义最优子问题:

    定义最优子问题,也就是找问题的优化目标以及用什么样的决策才能得到最优解,并对决策阶段进行划分。
    所谓阶段,可以理解为解决一个问题所要经过的步骤(环节),这些步骤前后相关联。划分阶段同样也没有固定的模式,需要具体问题具体分析。

2、定义状态:

    状态既是决策的对象,同时也是决策的结果。对于每一个阶段来说,对起始状态加以决策,使状态发生改变得到决策后的结果状态。初始状态经过一系列的决策之后得到的状态就是这个问题的解。但是,并不是所有的决策施加于初始状态都能得到最优解,只有其中一个决策序列能得到最优解。状态的定义是建立在子问题定义的基础之上的,因此必须满足“无后效性”这个要求。必要的时候,可以增加状态的纬度引入更多的约束条件来使得状态的定义满足“无后效性”这个要求。

3、定义决策和状态转移方程:

    所谓决策,是指能够使状态发生转变的选择动作,如果选择动作有多个,那么决策就是这多个动作中可以得到阶段最优解的那一个。
    所谓状态转换方程,就是描述状态转换关系的一系列等式。也就是从n-1阶段演化为n阶段的演化规律。状态转换取决于子问题的堆叠方式,如果状态定义得不合理,那么就会导致子问题之间没有重叠的部分,也就不存在状态转换关系了,自然也不存在状态转换方程。动态规划也就失去了意义。

4、确定边界条件:

    对于记忆搜索实现的动态规划方法,边界条件就是递归终止的条件。对于使用递推关系直接实现的动态规划方法,需要确定状态转换方程的递推式的初始条件或者边界条件,否则无法开始计算。

下面我们来看一道动态规划入门经典的题目:数字三角形。

              The Triangle POJ - 1163

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.


Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.


Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30

题意:

    在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可,不必给出具体路径。三角形的行数大于1小于等于100,数字为 0 - 99。

解题思路:

    1. 用一个二维数组存来放数字三角形。
    2. D( r, j) : 第r行第 j 个数字(r,j从1开始算)
    3. MaxSum(r, j) : 从D(r,j)到底边的各条路径中,最佳路径的数字之和。
这样,问题就变成了求解 MaxSum(1,1)

这是一道典型的递归问题。

D(r, j)出发,下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形:
    if ( r == N)
      MaxSum(r,j) = D(r,j)
    else
      MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)

思路有了,那我们就来写一下代码吧:

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1000;

int d[MAX][MAX];
int n;

int MaxSum(int i, int j)
{
    if (i==n) return d[i][j];
    return max(MaxSum(i+1,j),MaxSum(i+1,j+1)) + d[i][j];
}

int main(int argc, char const *argv[])
{
    while(cin>>n && n) {
        for(int i=1; i <= n; i++)
            for(int j = 1; j <= i; j++)
                cin>>d[i][j];

        cout << MaxSum(1,1) << endl;
    }
    return 0;
}

让我们看看结果如何:

结果是正确的。那我们提交一下代码试试?

哎,这就尴尬了,超时!为什么会超时呢?

下面我们就来分析一下:

先来上个分析图:

               

    在计算d[1][1](也就是“7”)的时候,会先计算出从底部到第二层(3、8这一层)的路径数字之和,看看是从“3”这里上来再加上d[1][1]大还是从“8”这里上来比较大,最后取最大的那个。此时“3”和“8”所在路径分别被计算了一次,依次计算下去,我们注意到,在计算从底部到第三层(8、1、0)的时候呢,在计算到第二层的3时,第三层的1所在路径被计算一次,在计算第二层的8时,第三层的1所在路径被计算一次,加起来就计算了两次。再这么推下去,发现越靠下层的数所在路径的计算次数越来越大,而这种重复计算显然是不必要的。这就是我们代码超时的原因!代码运行过程中存在大量的重复计算。对于n==100这种数量级,代码肯定会超时。
    
    既然找到了原因,那么我们就可以对症下药了。
    
    我们人类伟大的物理学家爱因斯坦就认为时间和空间可以互相转换。其实我们的程序也是如此。可以牺牲一些空间来换取运行时间的减少。
    
    我们可以设置一个与d同样大的二维数组result来存放计算的结果,然后在程序运行时,如果该结果已经被计算过了,就直接在递归函数MaxSum中返回这个值就可以了,不用重新计算。怎么知道该值有没有被计算过呢?
    嗯,根据题目的意思,题目所给的数都是正数,那不如我们将数组result初始化为-1,只要result[i][j]的值大于-1,就说明被计算过了嘛。
    那。。。。。。我们试试?嘿嘿~

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 1000;

int d[MAX][MAX], result[MAX][MAX];
int n;

int MaxSum(int i, int j)
{
    if (i==n) return d[i][j];
    if (result[i][j] > -1) return result[i][j];
    return result[i][j] = max(MaxSum(i+1,j),MaxSum(i+1,j+1)) + d[i][j];
}

int main(int argc, char const *argv[])
{
    while(cin>>n && n) {
        for(int i=1; i <= n; i++)
            for(int j = 1; j <= i; j++)
                cin>>d[i][j];

        memset(result,-1, sizeof result);   //记得初始化成-1哈(用这个函数来初始化只能用-1或者0,用其他的值的话初始化的结果可不是你想得到的结果哦,而且要包含头文件cstring)

        cout << MaxSum(1,1) << endl;
    }
    return 0;
}

看看样例过没过哈。

嗯,样例过了,看看poj过没有。

哎,果然过了哈。

嗯,递归的写法搞定了,学过动态规划的人都知道,这道题还有种递推的写法。我们来试试?

通过分析,我们发现了这样的一个事实:

    我们从最底层,也就是第n(i从1开始,n==5)从开始看起,我们发现,这个问题的边界就是第n层各个位置节点的值。因为第n层是最后一层了嘛,它的下面已经没有了路径。根据我们定义的状态转移方程
    if ( r == N)
      MaxSum(r,j) = D(r,j)
    else
      MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)
就可以窥出端倪之处:
    result[i][j]是等于max(result[i+1][j], result[i+1][j+1]) + d[i][j];的,即result[i][j]的值等于它正下方和右下方最大的那个节点的值加上它自己所在节点的值。上面的右图就是result,左图是三角形。
    
    result第4层的“7”等于三角形中max(4,5) + 2; “12” = max(5,2)+7; “10” = max(2,6) + 4; “10” = max(6,5) + 4;……………………就这样层层递推上去,发现,最后result[1][1]的值就是我们要求的解。
    因此,我们有了下面的代码:

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1000;

int d[MAX][MAX], result[MAX][MAX];
int n;

int main(int argc, char const *argv[])
{
    while(cin>>n && n) {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i; j++)
                cin>>d[i][j];

        for(int i = 1; i <= n; i++)//记得这个边界处理,不然得不到正确答案
            result[n][i] = d[n][i];

        for(int i = n-1; i >= 1; i--)
            for(int j = 1; j <= i; j++)
                result[i][j] = max(result[i+1][j],result[i+1][j+1]) + d[i][j];

        cout << result[1][1] << endl;
    }
    return 0;
}

这个代码提交也是能过的,我就不上图了。

下面我们谈谈递归和递推的优缺点:
    递归看起来比较简洁,对于上面给的递归代码,其实还可以这么写:
    

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 100 + 5;

int Trigngle[MAX][MAX];
int d[MAX][MAX];
int n = 0;

int dp(int i, int j)
{
    if (d[i][j] >= 0) return d[i][j];
    return d[i][j] = (n == i) ? 0 : Trigngle[i][j] + max(dp(i + 1, j), dp(i + 1, j + 1));
}

int main()
{
    while (cin >> n && n) {
        memset(d, -1, sizeof d);
        memset(Trigngle, 0, sizeof  Trigngle);
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= i; j++)
                cin >> Trigngle[i][j];

        cout << dp(0, 0) << endl;
    }

    return 0;
}

    你看,递归函数里只有两行,够简洁吧(这参照了刘汝佳给出的方法和代码风格)。然而事物总是不完美的。递归因为有额外的函数调用开销,所以它的效率总数要比递推循环要慢一点点,而且递归层数过深的话还可能会爆栈。。。。
    使用递推的话,效率是高那么一点,而且还有一种叫做“滚动数组”的骚操作可以用,嘿嘿~
    
    既然提到了就顺带说一下滚动数组。
    
    

    没必要用二维result数组存储每一个MaxSum(r,j),只要从底层一行行向上递推,那么只要一维数组result[MAX]即可,即只要存储一行的MaxSum值就可以了。
    我们将第4层“2”计算出来的“7”放到result的第1个位置,result数组就成了
然后我们接着算第四层“7”计算出来的“12”放在result的第2个位置,此时
依次计算:



到此,我们就计算完成了第四层的结果。蓝色的数字就是第四层的结果,可以和下面完整的结果对比一下,帮助理解。



    再这样一直递推计算下去,第2层的结果这样的:
    
    最后的结果是 max(20,13) + d[1][1](也就是7)== 30,这就是最终结果。我们从尾到头计算下来,是不是有点像一个一维数组从底部“滚动”到了头部?这就是“滚动数组”的由来。
    
    其实这道题目还有更骚的操作。咳咳。。。。。不知道友可曾发现,这样递推计算,其实d[n][j]的值只在计算d[n-1][j]和d[n-1][j-1]的时候有用,在计算完成之后,二维数组d最后一层的值用不上了。俗话说得好,闲着也是浪费,出门不捡就是丢不是~嘿嘿,反正闲着也是闲着,我就用用它呗。
    
    我就弄个指针result指向数组d这一层,用这一层来像滚动数组那样存储计算的结果,这样还省去了额外的数组result的开销。美滋滋不是?咳咳。。。。
    
    下面就给出代码:
    

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1000;

int d[MAX][MAX];

int main(int argc, char const *argv[])
{
    int n;

    while(cin>>n && n) {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i; j++)
                cin>>d[i][j];

        int *result = d[n];//骚操作在这里

        for(int i = n-1; i >= 1; i--)
            for(int j = 1; j <= i; j++)
                result[j] = max(result[j],result[j+1]) + d[i][j];

        cout << result[1] << endl;
    }
    return 0;
}

这道题目就讲解到这。

    动态规划对于初学者来说是个不小的挑战,其难点在于状态的定义,以及状态转换方程的建立。还有就是对“无后效性”和“最优子结构”这两个概念的理解。

    动态规划的解题没有固定的套路,只有具体问题具体分析。我们也应该要做到学东西学的是思想和方法,而不是僵硬的解题模式和死板的答案。只有通过大脑思考过的东西,方能真正为我们所用。