论文部分内容阅读
[摘要]动态规划算法是计算机领域中一种非常有效的算法，而对于很多要掌握它的学生而言，往往会表现出很大的困惑性，本文介绍了动态规划算法的三种表达技巧，并详细阐述了较难掌握的部分存储的动态规划算法。
[关键词]子问题 辅助存储单元 全部存储 部分存储
一、引言
动态规划算法是一种以空间换取时间的算法，这里的空间即指计算过程中所用到的辅助存储单元。
经过我们多次分析发现，动态规划算法通常有三种表示形式，并且它们具有相同的时间复杂度和可供选择的空间复杂度。选择不同的空间复杂度，即选择了不同数量级的内存分配。对于一个算法而言，通常考虑较多是的其时间复杂度，而动态规划算法，其空间复杂度却非常值得深入考虑，能否减少辅助存储单元，并在它的前提下尽可能让算法时间复杂度得到优化，是一个值得分析的问题。
本论文首先介绍动态规划算法的三种写法，然后对其中的一种写法进行深入分析，介绍如何减小空间复杂度的方法，并结合acm竞赛问题，介绍了一种利用指针技巧减少运算量的方法，使得算法在减少内存的同时仅仅增加了微不足道的运算量。
二、动态规划算法的三种常用写法
能够运用动态规划算法求解的问题都可以用一个递推关系式来表达，此递推关系的基本原理即是：将所要求解的原始问题分解成规模较小的子问题来做，而子问题可以依据同样的分解原理分解成更小的子问题，直到不能分解为止，不能继续分解的问题称为最小规模的子问题，它的结果是已知的，按照分解的逆过程，由小规模子问题的结果可以推算出较大规模子问题的结果，直至最终推算出原始问题的结果。这个递推关系式其实就是一种递归描述，并且递归描述中用来表示子问题的部分必然是是重复出现的。
动态规划算法的本质就是用一些辅助存储单元将这些重复出现的子问题结果保存起来，在每一个子问题第一次被计算出来后存储在其相应单元中，如果在后续计算过程中，一个已经有结果的子问题被要求再次计算时，动态规划算法就直接取用已经存储的结果，而不是像原始递归一样去重复计算，这样就保证了一个子问题只计算一次，从而大大减少了运算量。对于一个只有n个子问题的原始问题，原始递归往往会付出指数数量级的运算代价，而动态规划只需要付出Θ(n)的运算代价（假设算出一个子问题结果需要时间为Θ(1)）。
例如，斐波那契数列的递归描述为：
其中n为正整数，f(n)表示数列中第n项的值，为方便算法表达，假定n<100，不考虑整数溢出问题，其递归和三种动态规划算法分别如下。
递归写法的时间复杂度为Θ( )，空间复杂度为Θ(n)，动态规划的三种写法时间复杂度均为Θ(n)，其中写法一与写法二的空间复杂度是Θ(n)，而写法三的空间复杂度是Θ(1)，它比前两种写法的空间复杂度要低一个数量级。换一个角度讲，写法一与写法二是存储所有子问题的动态规划算法，而写法三是存储部分子问题的动态规划算法。
在运用动态规划算法解决问题时，辅助存储单元的数量级可以根据具体情况进行选择。如果所有子问题的数量级太大而超出存储要求，可以考虑低一个数量级存储的动态规划算法，虽然这种写法可以计算出某一个目标值，但是由于它所对应的存储单元被反复改写，保留的信息是有限的。例如，上面动态规划算法写法一和写法二，不仅求解保存了第n项的值，其前n-1项的值都被计算保存了，而写法三虽然计算出了第n项的值和前面相邻第n-1项的值，但是前n-2项的值已经无法获取，因此，这种节省内存的算法只适合于求解目标值较少的问题。
三、时间、空间复杂度的分析及改进策略
动态规划算法的时间、空间复杂度主要取决于子问题的个数，子问题个数由递推关系式中反映问题规模的参变量决定，其时间复杂度与子问题个数成正比，而空间复杂度取决于对子问题结果的存储方式。一般而言，对子问题结果进行全部存储，是最为常用的一种策略，可以在此基础上提出一种改进策略为部分存储。有些问题需要存储全部的子问题，才能完成目标计算任务，而有些问题可以只用存储部分子问题，即可完成目标计算任务。
1.时间复杂度分析
动态规划算法的时间复杂度（记为T(n)）取决于所有子问题个数的数量级（记为C(n)）和每一个子问题被计算出需要付出的时间代价（记为x(n)），那么以上三种写法的动态规划算法的时间复杂度相同，并且均为公式一。
T(n)=C(n)*x(n) （公式一）
2.空间复杂度分析
类似于时间复杂度分析，动态规划算法的空间复杂度（记为G(n)）取决于所有子问题个数的数量级（记为C(n)）和存储一个子问题所用的存储代价（记为g(n)），那么存储所有子问题的动态规划算法空间复杂度为公式二。
G(n)=C(n)*g(n) （公式二）
3.改进策略
对上面空间复杂度的一种改进策略是，采用部分存储的方式，将空间复杂度中的C(n)降低到C’(n)，其对应计算式为公式三。
G(n)=C’(n)*g(n) （公式三）
例如一个子问题个数为n2的问题，存储所有子问题时，通常可以用n×n大小的二维数组，其空间复杂度为θ(n2)；存储部分子问题时，可以只存储该n×n方阵中的一行（列）或几行（列），其空间复杂度为θ(n)。前面介绍的费波那契数列的动态规划算法写法三，即是将空间复杂度由θ(n)降低到θ(1)之后的一种结果。
部分存储的改进策略，一般可以将空间复杂度降低一维，尤其是当n较大时，这种降维的效果会非常明显。空间复杂度降低一维之后的动态规划写法，可以模仿前面的写法三。
四、改进策略的应用
一般情况下，存储部分子问题比存储所有子问题的动态规划算法要付出更多的运算量，甚至可能会高出一个数量级，但是，可以结合一些特殊技巧改进运算量，使其空间复杂度保持在公式一的情况。下面结合北大ACM网站上的一道题目1159，介绍动态规划算法改进策略的运用。
求往一个字符串中最少插入多少个字符可以使其变成回文字符串[1]。分析过程如下，假设字符串为a[1]～a[n]，其长度为n，用f(i,j)表示a[i]～a[j]部分要变成回文需要插入的最少字符个数，其中1≤i≤j≤n，f(1,n)即为原始问题，则有如下递归描述：
由递推式可知，对子问题全部存储的空间复杂度是θ(n2)，其对应f(i,j)在存储矩阵中的逻辑关系如下图。
根据动态规划算法思想和递推式分析，在计算f(i,j)之前，必须保证f(i,j-1)，f(i+1,j-1)，f(i+1,j)已经被计算出并被保存，因此对于此矩阵中上三角部分的求解，其计算顺序可以采用从下往上逐行计算，每一行元素计算时从左往右进行的方式；另外，部分存储策略中最节省存储单元的方法是，只保存在计算顺序上从f(i+1,j-1)到f(i,j)范围内的子问题结果，其算法是每计算出一个f(i,j)准备计算下一项f(i,j+1)时，将f(i+1,j-1)到f(i,j)范围对应的存储单元循环迭代，从而运用同样的循环语句完成整个计算过程，最后计算的一项即是右上角的原始问题f(1,n)。
为了避免这里面的循环迭代计算，可以采用与最节省存储单元等数量级的另外一种部分存储策略，即存储图中从f(i+1,j-1)到f(i,j)范围内所有行的子问题结果，算法中用p1,p分别表示这两行，显然，p行中子问题f(i,j)对应的元素为p[j]，其它子问题对应元素同理。当p行计算结束后，按子问题计算顺序算法会接着计算p行的上面一行，我们对p,p1采用指针的技巧，当p行计算结束后，交换一下p与p1所指向的存储单元即可，从而减少对存储单元反复迭代的计算部分，其算法实现如下面代码所示。
五、结束语
本文对动态规划算法的空间复杂度提出了一种改进思路，并结合程序设计竞赛问题阐述了这种策略的详细设计过程，与广大师生，尤其是参加程序设计竞赛的学生，共同探讨了动态规划算法的表达技巧和改进技巧。
[参考文献]
[1] http://poj.org/problem?id=1159
（作者单位：1.湖北经济学院信息管理学院,2.武汉大学珞珈学院）
[关键词]子问题 辅助存储单元 全部存储 部分存储
一、引言
动态规划算法是一种以空间换取时间的算法，这里的空间即指计算过程中所用到的辅助存储单元。
经过我们多次分析发现，动态规划算法通常有三种表示形式，并且它们具有相同的时间复杂度和可供选择的空间复杂度。选择不同的空间复杂度，即选择了不同数量级的内存分配。对于一个算法而言，通常考虑较多是的其时间复杂度，而动态规划算法，其空间复杂度却非常值得深入考虑，能否减少辅助存储单元，并在它的前提下尽可能让算法时间复杂度得到优化，是一个值得分析的问题。
本论文首先介绍动态规划算法的三种写法，然后对其中的一种写法进行深入分析，介绍如何减小空间复杂度的方法，并结合acm竞赛问题，介绍了一种利用指针技巧减少运算量的方法，使得算法在减少内存的同时仅仅增加了微不足道的运算量。
二、动态规划算法的三种常用写法
能够运用动态规划算法求解的问题都可以用一个递推关系式来表达，此递推关系的基本原理即是：将所要求解的原始问题分解成规模较小的子问题来做，而子问题可以依据同样的分解原理分解成更小的子问题，直到不能分解为止，不能继续分解的问题称为最小规模的子问题，它的结果是已知的，按照分解的逆过程，由小规模子问题的结果可以推算出较大规模子问题的结果，直至最终推算出原始问题的结果。这个递推关系式其实就是一种递归描述，并且递归描述中用来表示子问题的部分必然是是重复出现的。
动态规划算法的本质就是用一些辅助存储单元将这些重复出现的子问题结果保存起来，在每一个子问题第一次被计算出来后存储在其相应单元中，如果在后续计算过程中，一个已经有结果的子问题被要求再次计算时，动态规划算法就直接取用已经存储的结果，而不是像原始递归一样去重复计算，这样就保证了一个子问题只计算一次，从而大大减少了运算量。对于一个只有n个子问题的原始问题，原始递归往往会付出指数数量级的运算代价，而动态规划只需要付出Θ(n)的运算代价（假设算出一个子问题结果需要时间为Θ(1)）。
例如，斐波那契数列的递归描述为：
其中n为正整数，f(n)表示数列中第n项的值，为方便算法表达，假定n<100，不考虑整数溢出问题，其递归和三种动态规划算法分别如下。
递归写法的时间复杂度为Θ( )，空间复杂度为Θ(n)，动态规划的三种写法时间复杂度均为Θ(n)，其中写法一与写法二的空间复杂度是Θ(n)，而写法三的空间复杂度是Θ(1)，它比前两种写法的空间复杂度要低一个数量级。换一个角度讲，写法一与写法二是存储所有子问题的动态规划算法，而写法三是存储部分子问题的动态规划算法。
在运用动态规划算法解决问题时，辅助存储单元的数量级可以根据具体情况进行选择。如果所有子问题的数量级太大而超出存储要求，可以考虑低一个数量级存储的动态规划算法，虽然这种写法可以计算出某一个目标值，但是由于它所对应的存储单元被反复改写，保留的信息是有限的。例如，上面动态规划算法写法一和写法二，不仅求解保存了第n项的值，其前n-1项的值都被计算保存了，而写法三虽然计算出了第n项的值和前面相邻第n-1项的值，但是前n-2项的值已经无法获取，因此，这种节省内存的算法只适合于求解目标值较少的问题。
三、时间、空间复杂度的分析及改进策略
动态规划算法的时间、空间复杂度主要取决于子问题的个数，子问题个数由递推关系式中反映问题规模的参变量决定，其时间复杂度与子问题个数成正比，而空间复杂度取决于对子问题结果的存储方式。一般而言，对子问题结果进行全部存储，是最为常用的一种策略，可以在此基础上提出一种改进策略为部分存储。有些问题需要存储全部的子问题，才能完成目标计算任务，而有些问题可以只用存储部分子问题，即可完成目标计算任务。
1.时间复杂度分析
动态规划算法的时间复杂度（记为T(n)）取决于所有子问题个数的数量级（记为C(n)）和每一个子问题被计算出需要付出的时间代价（记为x(n)），那么以上三种写法的动态规划算法的时间复杂度相同，并且均为公式一。
T(n)=C(n)*x(n) （公式一）
2.空间复杂度分析
类似于时间复杂度分析，动态规划算法的空间复杂度（记为G(n)）取决于所有子问题个数的数量级（记为C(n)）和存储一个子问题所用的存储代价（记为g(n)），那么存储所有子问题的动态规划算法空间复杂度为公式二。
G(n)=C(n)*g(n) （公式二）
3.改进策略
对上面空间复杂度的一种改进策略是，采用部分存储的方式，将空间复杂度中的C(n)降低到C’(n)，其对应计算式为公式三。
G(n)=C’(n)*g(n) （公式三）
例如一个子问题个数为n2的问题，存储所有子问题时，通常可以用n×n大小的二维数组，其空间复杂度为θ(n2)；存储部分子问题时，可以只存储该n×n方阵中的一行（列）或几行（列），其空间复杂度为θ(n)。前面介绍的费波那契数列的动态规划算法写法三，即是将空间复杂度由θ(n)降低到θ(1)之后的一种结果。
部分存储的改进策略，一般可以将空间复杂度降低一维，尤其是当n较大时，这种降维的效果会非常明显。空间复杂度降低一维之后的动态规划写法，可以模仿前面的写法三。
四、改进策略的应用
一般情况下，存储部分子问题比存储所有子问题的动态规划算法要付出更多的运算量，甚至可能会高出一个数量级，但是，可以结合一些特殊技巧改进运算量，使其空间复杂度保持在公式一的情况。下面结合北大ACM网站上的一道题目1159，介绍动态规划算法改进策略的运用。
求往一个字符串中最少插入多少个字符可以使其变成回文字符串[1]。分析过程如下，假设字符串为a[1]～a[n]，其长度为n，用f(i,j)表示a[i]～a[j]部分要变成回文需要插入的最少字符个数，其中1≤i≤j≤n，f(1,n)即为原始问题，则有如下递归描述：
由递推式可知，对子问题全部存储的空间复杂度是θ(n2)，其对应f(i,j)在存储矩阵中的逻辑关系如下图。
根据动态规划算法思想和递推式分析，在计算f(i,j)之前，必须保证f(i,j-1)，f(i+1,j-1)，f(i+1,j)已经被计算出并被保存，因此对于此矩阵中上三角部分的求解，其计算顺序可以采用从下往上逐行计算，每一行元素计算时从左往右进行的方式；另外，部分存储策略中最节省存储单元的方法是，只保存在计算顺序上从f(i+1,j-1)到f(i,j)范围内的子问题结果，其算法是每计算出一个f(i,j)准备计算下一项f(i,j+1)时，将f(i+1,j-1)到f(i,j)范围对应的存储单元循环迭代，从而运用同样的循环语句完成整个计算过程，最后计算的一项即是右上角的原始问题f(1,n)。
为了避免这里面的循环迭代计算，可以采用与最节省存储单元等数量级的另外一种部分存储策略，即存储图中从f(i+1,j-1)到f(i,j)范围内所有行的子问题结果，算法中用p1,p分别表示这两行，显然，p行中子问题f(i,j)对应的元素为p[j]，其它子问题对应元素同理。当p行计算结束后，按子问题计算顺序算法会接着计算p行的上面一行，我们对p,p1采用指针的技巧，当p行计算结束后，交换一下p与p1所指向的存储单元即可，从而减少对存储单元反复迭代的计算部分，其算法实现如下面代码所示。
五、结束语
本文对动态规划算法的空间复杂度提出了一种改进思路，并结合程序设计竞赛问题阐述了这种策略的详细设计过程，与广大师生，尤其是参加程序设计竞赛的学生，共同探讨了动态规划算法的表达技巧和改进技巧。
[参考文献]
[1] http://poj.org/problem?id=1159
（作者单位：1.湖北经济学院信息管理学院,2.武汉大学珞珈学院）