动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章，大多都是叙述概念，讲解原理，让人觉得晦涩难懂，即使一时间看懂了，发现当自己做题的时候又会觉得无所适从。我觉得，理解算法最重要的还是在于练习，只有通过自己练习，才可以更快地提升。话不多说，接下来，下面我就通过一个例子来一步一步讲解动态规划是怎样使用的，只有知道怎样使用，才能更好地理解，而不是一味地对概念和原理进行反复琢磨。
首先，我们看一下这道题（此题目来源于北大POJ）：
数字三角形(POJ1163)
在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100，数字为 0 - 99
输入格式：
5 //表示三角形的行数 接下来输入三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 要求输出最大和
接下来，我们来分析一下解题思路：
首先，肯定得用二维数组来存放数字三角形
然后我们用D( r, j) 来表示第r行第 j 个数字(r,j从1开始算)
我们用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>
#define MAX 101
using namespace std;
int D[MAX][MAX];
int n;
int MaxSum(int i, int j){
if(i==n)
return D[i][j];
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
return max(x,y)+D[i][j];
}
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin >> D[i][j];
cout << MaxSum(1,1) << endl;
}
对于如上这段递归的代码，当我提交到POJ时，会显示OLE
对的，代码运行超时了，为什么会超时呢？
答案很简单，因为我们重复计算了，当我们在进行递归时，计算机帮我们计算的过程如下图：
就拿第三行数字1来说，当我们计算从第2行的数字3开始的MaxSum时会计算出从1开始的MaxSum，当我们计算从第二行的数字8开始的MaxSum的时候又会计算一次从1开始的MaxSum，也就是说有重复计算。这样就浪费了大量的时间。也就是说如果采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为 2的n次方,对于 n = 100 行，肯定超时。
接下来，我们就要考虑如何进行改进，我们自然而然就可以想到如果每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用n方的时间复杂度完成计算。因为三角形的数字总数是 n(n+1)/2
根据这个思路，我们就可以将上面的代码进行改进，使之成为记忆递归型的动态规划程序：
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];
int MaxSum(int i, int j){
if( maxSum[i][j] != -1 )
return maxSum[i][j];
if(i==n)
maxSum[i][j] = D[i][j];
else{
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
maxSum[i][j] = max(x,y)+ D[i][j];
}
return maxSum[i][j];
}
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++) {
cin >> D[i][j];
maxSum[i][j] = -1;
}
cout << MaxSum(1,1) << endl;
}
当我们提交如上代码时，结果就是一次AC
虽然在短时间内就AC了。但是，我们并不能满足于这样的代码，因为递归总是需要使用大量堆栈上的空间，很容易造成栈溢出，我们现在就要考虑如何把递归转换为递推，让我们一步一步来完成这个过程。
我们首先需要计算的是最后一行，因此可以把最后一行直接写出，如下图：
现在开始分析倒数第二行的每一个数，现分析数字2，2可以和最后一行4相加，也可以和最后一行的5相加，但是很显然和5相加要更大一点，结果为7，我们此时就可以将7保存起来，然后分析数字7，7可以和最后一行的5相加，也可以和最后一行的2相加，很显然和5相加更大，结果为12，因此我们将12保存起来。以此类推。。我们可以得到下面这张图：
然后按同样的道理分析倒数第三行和倒数第四行，最后分析第一行，我们可以依次得到如下结果：
上面的推导过程相信大家不难理解，理解之后我们就可以写出如下的递推型动态规划程序：
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin >> D[i][j];
for( int i = 1;i <= n; ++ i )
maxSum[n][i] = D[n][i];
for( int i = n-1; i>= 1; --i )
for( int j = 1; j <= i; ++j )
maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];
cout << maxSum[1][1] << endl;
}
我们的代码仅仅是这样就够了吗？当然不是，我们仍然可以继续优化，而这个优化当然是对于空间进行优化，其实完全没必要用二维maxSum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以。
对于空间优化后的具体递推过程如下：
接下里的步骤就按上图的过程一步一步推导就可以了。进一步考虑，我们甚至可以连maxSum数组都可以不要，直接用D的第n行直接替代maxSum即可。但是这里需要强调的是：虽然节省空间，但是时间复杂度还是不变的。
依照上面的方式，我们可以写出如下代码：
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int * maxSum;
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin >> D[i][j];
maxSum = D[n]; //maxSum指向第n行
for( int i = n-1; i>= 1; --i )
for( int j = 1; j <= i; ++j )
maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j];
cout << maxSum[1] << endl;
}
接下来，我们就进行一下总结：
递归到动规的一般转化方法
递归函数有n个参数，就定义一个n维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。
动规解题的一般思路
1. 将原问题分解为子问题
把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决(数字三角形例）。
子问题的解一旦求出就会被保存，所以每个子问题只需求 解一次。
2.确定状态
在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状 态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状 态”所对应的子问题的解。
所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。 在数字三角形的例子里，一共有N×(N+1)/2个数字，所以这个问题的状态空间里一共就有N×(N+1)/2个状态。
整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。在数字三角形里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。
3.确定一些初始状态（边界状态）的值
以“数字三角形”为例，初始状态就是底边数字，值就是底边数字值。
4. 确定状态转移方程
定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”(递推型)。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。
数字三角形的状态转移方程:
能用动规解决的问题的特点
1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结 构性质。
2) 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。利用各个阶段之间的关系，逐个求解，最终求得全局最优解，需要确认原问题与子问题、动态规划状态、边界状态、边界状态结值、状态转移方程。
一、爬楼梯
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
方法一：利用n个楼梯的步数，与n-1还有n-2之间的关系可以退出，f(n)==f(n-1)+f(n-2),相当于是直接考虑为n-1再上一步，和n-2直接上两步，不能考虑n-2有两种走法（一步一步，和一次两步，一步一步的会和n-1中的重复，导致算多了），最后不断的迭代直至可以n==1或者n==2，可以直接求出结果。
这个方法相当于是根据各个阶段之间的关系，列出迭代关系，并且写出临界解，从而结束递归的过程，否则将一直递归下去（所有的递归都是如此，如果没有边界条件提前结束递归，递归将不会停止）
这个时间复杂度是2^n相当于是一颗二叉树来着，leetcode显示time limit exceed
int climbStairs(int n) {
if(n==1||n==2){
return n;
}
return climbStairs(n-1)+climbStairs(n-2);
}
方法二：利用迭代来实现尾递归
由于方法一是利用了尾递归来实现算法，考虑采用迭代来实现递归，并且递归本身算法复杂度是要远远大于其对应的迭代循环算法复杂度的，所以考虑利用迭代来减少时间复杂度。两种方法的差别在于递归是从上往下算，迭代是从下往上算。
class Solution {
public:
int climbStairs(int n) {
vector<int>iteration(n+1,0); //initializition
iteration[1]=1;
iteration[2]=2;
int i=3;
while(i<n+1){
iteration[i]=iteration[i-1]+iteration[i-2];
i++;
}
return iteration[n];
}
};
时间复杂度是O(n)，相比较于尾递归大大优化，leetcode显示ac。
二、抢劫犯问题
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
题目分析：这个题目的分析关键在于DP算法中状态转移方程的求解，也就是求解是迭代关系，可以发现对于第i个房间而言，如果不抢劫第i个房间那么就是i-1个的抢劫数目，如果抢劫第i个房间那么就是一定不能抢劫i-1个房间，相当于是i-2个房间的抢劫数目，两者时间的最大值即可，从而成功得出迭代关系。
注意自身在分析问题时的错误：
一：在无法的出迭代关系的情况下，没有考虑根据题意堆可能的情况进行分类，注意两个题目都是进行了分类的讨论，才得以顺利的得出迭代关系，并且盲目的理解为迭代关系一定是两者之间的和，没有考虑到最大值得情况。
二：在考虑迭代关系时一定要思考如何引入第i-1个和第i-2个问题的解，这道题就是通过分类讨论，成功剥离出了i-1和i-2的情况；迭代关系的另一个要素是如何把i与i-1和i-2之间的关系找到
三：在考虑迭代关系时一定把i考虑成足够大，因为在代码实现过程中i很小的情况是直接给出的，直接赋值的（对于有dp数组而言），i很小的情况下只是考虑为边界条件，作为循环的起始或者是迭代的结束。所以考虑迭代关系时一定不要具体化i而是直接假设i足够大去考虑。
求取迭代关系的步骤：
1、根据题意分类讨论，分类讨论一定要达到引入i-1和i-2的解
2、挖掘i和i-1还有i-2之间的关系
3、边界条件确认
方法一、使用迭代法
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty()) return 0;
if(nums.size()==1) return nums[0];
vector<int>dp(nums.size(),0);
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<nums.size();i++){
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.size()-1];
}
};
时间复杂度为O（n）,运行时间3ms
方法二、使用递归算法
class Solution {
public:
int rob(vector<int>& nums) {
int size=nums.size();
if(size==0) return 0;
if(size==1) return nums[0];
if(size==2) return max(nums[0],nums[1]);
vector<int>a1(nums.begin(),nums.end()-1);
vector<int>a2(nums.begin(),nums.end()-2);
return max(rob(a1),rob(a2)+nums[size-1]);
}
};
可以发现这种方法再次出现了time limit exceed，时间复杂度是O(2^n),以后不用再考虑递归的DP算法了，直接使用迭代，时间复杂度降低很多。
三、最大子段和
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
注意自身在分析问题时的错误：
在分析问题的时候没有灵活变通，直接考虑前i个连续子数组数组的最大值，将无法进行分类讨论，无法得到递归关系，并且在考虑递归关系时也是直接考虑了i与i-1还有i-2之间的关系，其实可以考虑为i与i-1的关系即可，只要是一种可以迭代出所有情况的关系即可。在不能够得出迭代关系的时候需要变通的考虑，改变dp数组的意义，不需要一步到位，只要保证可以通过dp数组得到最后的结果即可。
code：dp数组表示的是以第i个元素结尾的连续子数组的最大值，最后再寻找dp的最大值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int size=nums.size();
vector<int>dp(size,0);
dp[0]=nums[0];
for(int i=1;i<size;i++){
if(dp[i-1]>0) dp[i]=dp[i-1]+nums[i];
else dp[i]=nums[i];
}
int max1=dp[0];
for(int i=1;i<size;i++){
max1=max(max1,dp[i]);
}
return max1;
}
};
从第四题开始之后的题目都会较为复杂的情况
四、找零钱和
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.
注：这道题自己还是没有能够理解到迭代关系的思想，可以再看一下solution，此时实在无法理解
注意自身在分析问题时的错误：（假设已经理解了迭代关系）
一、这个迭代关系比较特殊，并不是i-1,i-2之类的，而是会变化的，随着coins的不同会发生改变，所以需要对coins进行遍历，在循环中加入条件判断顺便很好地解决了是否会越界的问题。
....没有理解这道题果然写不出总结
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,amount+1);
dp[0]=0;
for(int i=1;i<=amount;i++){
for(int m:coins){
if(m<=i) dp[i]=min(dp[i],dp[i-m]+1);
}
}
if(dp.back()==amount+1) return -1;
else return dp.back();
}
};
五、三角形
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).这道题目类似于第三题，都是对dp数组的意义进行转换，从而以退为进解决问题，这道题目是自己独立完成的，所以就不写心得了，直接上代码
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int size=triangle.size();
vector<vector<int>>dp(size,vector<int>(size,INT_MAX));
dp[0][0]=triangle[0][0];
for(int i=1;i<size;i++){
for(int j=0;j<triangle[i].size();j++){
if(j==0) dp[i][j]=dp[i-1][j]+triangle[i][j];
if(j==triangle[i].size()-1) dp[i][j]=dp[i-1][j-1]+triangle[i][j];
if(j!=0&&j!=triangle[i].size()-1) dp[i][j]=min(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]);
}
}
return *min_element(dp[size-1].begin(),dp[size-1].end());
}
};
京公网安备 11010502036488号