1.何为动态规划
动态规划（Dynamic Programming）是动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。
动态规划具备以下三个特点：
1. 把原来的问题分解成了几个相似的子问题。
2. 所有的子问题都只需要解决一次。
3. 储存子问题的解。
动态规划的本质，是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)。
在思考动态规划问题的时候，可以从这四个方向去思考：
1. 状态定义。
2. 状态间的转移方程定义。
3. 状态的初始化。
4. 返回结果。
对于状态定义的要求：定义的状态一定要形成递推关系。
动态规划一般的场景：适用场景：最大值/最小值, 可不可行, 是不是，方案个数。
2.题目练习
2.1、字符串分割
题目描述：
给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。
例如:
给定s=“nowcode”；
dict=["now", "code"].
返回true，因为"nowcode"可以被分割成"now code".
思路分析：
这个问题，问的就是这个字符串s是否能够被分割。
状态定义：我们可以用F(i)代表前i个字符串是否可以被分割。
状态转移方程：我们先来分析一下分割的过程以及判断是否可以被切割的结果。
F(3):前3个字符可以被切割，因为它是"now"，在字典中可以被找到。于是判定为true
F(7):F(3)&&[4,7]这段字符串是否可以被切割，可以的话，就是true;
设i和j，于是有以下判断过程：
F(1)&&[2,7];
F(2)&&[3,7];
F(4)&&[5,7];
F(5)&&[6,7];
F(6)&&[7,7];
F(0)&&[1,8]为一个整体。
通过上面的判断过程，就可以推出状态转移方程为:
F(i): true{ j <i && F(j) && substr[j+1,i]能在词典中找到 } OR false。在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典中找到，则F(i)为true。
初始值：我们使用vector作为容器，用来保存判断的结果。对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单的例子进行验证。因此初始化为F(0)=true;
返回值：F(s.size());
代码如下：
class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { if(s.empty()) { return false; } if(dict.empty()) { return false; } vector<bool> can_break(s.size()+1,false); //初始化为true can_break[0] = true; for(int i = 1;i<=s.size();++i) { for(int j = i-1;j>=0;--j) { if(can_break[j] && dict.find(s.substr(j,i-j))!=dict.end()) { can_break[i]=true; break; } } } return can_break[s.size()]; } };
2.2、三角矩阵
题目描述：
给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字。
例如，给出的三角形如下：
[[2],[3,4],[6,5,7],[4,1,8,3]]
最小的从顶部到底部的路径和是2 + 3 + 5 + 1 = 11。
注意：
如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。
思路分析：
状态:F[i,j]表示从(0,0)到(i,j)的最小路径和。
状态转移方程F(i,j):
由于在边缘部分的路径，只能从它的上一级走来，而中间的路可以由上一级的两个路径和中选择一个最小的。因此，分成两种情况：
①当j==0或者j==i,即在边缘部分的路，其状态转移方程F(i,j):
j==0:F(i-1,0)+F(i,j)；
j==i:F(i-1,j-1)+F(i,j);
②中间的路，其状态转移方程为F(i,j) = min( F(i-1,j), F(i-1,j-1) ) + F(i,j)；
初始状态：初始时，就F(0,0)自己。F(0,0) = triangle[0][0];
返回结果:在结果集中最后一行找到最小的那个。min(F(row-1, i));
代码如下：
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) { return 0; } //拷贝构造，对F[0][0]和F[i][j]初始化 vector<vector<int>> result(triangle); int row = 0,col = 0; for(row = 1;row<result.size();++row) { for(col = 0;col<=row;++col) { //边界 if(col==0) { result[row][col] = result[row-1][0]+result[row][col]; } else if(col==row) { result[row][col] = result[row-1][col-1]+result[row][col]; } else //非边界 { result[row][col] = min(result[row-1][col],result[row-1][col-1])+result[row][col]; } } } //取最小值 int min_result = result[result.size()-1][0]; for(int i = 1;i<result.size();++i) { if(min_result > result[result.size()-1][i]) { min_result = result[result.size()-1][i]; } } return min_result; } };
2.3、路径总数
题目描述：
一个机器人在m×n大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？
备注：m和n小于等于100,并保证计算结果在int范围内
数据范围：0 < n,m \le 1000<n,m≤100，保证计算结果在32位整型范围内
要求：空间复杂度 O(nm)O(nm)，时间复杂度 O(nm)O(nm)
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(min(n,m))O(min(n,m))
思路分析：
状态F(i,j)表示从(0,0)到(i,j)的路径数。
状态转移方程：因为只能向下走或者向右走。因此，可以分成两种情况：
①当在边界，即i==0或j==0的时候，路径数只有1条。这也是初始值。
F(i, 0) = 1;
F(0, j) = 1;
②不在边界，对于每一个(i,j)的路径数，是把向上的总路径数+向左的总路径数。
F(i,j) = F(i-1,j) +F(i,j-1);
返回结果：F(row-1,col-1);
代码如下：
int uniquePaths(int m, int n) { // write code here if(m<0 || n<0) { return 0; } //开辟空间并初始化 vector<vector<int>> tmp(m,vector<int>(n,1)); for(int i = 1;i<m;++i) { for(int j = 1;j<n;++j) { tmp[i][j] = tmp[i-1][j]+tmp[i][j-1]; } } int result = tmp[m-1][n-1]; return result; }
2.4、最小路径和
题目描述：
给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。
注意：你每次只能向下或向右移动。
思路分析：
这道题与上一道题思路很相似。算是第二道题和第三道题的结合，找最小路径的权值的和。
状态F(i,j)表示从(0,0)到达F(i,j)的最短路径。
状态转移方程：因为只能向下或向右移动。因此有两种情况：
①边界：即i==0和j==0的情况。这种情况每次都是只能从它的正上一级走来。
F(i,0) = F(i-1,0)+F(i,0);
F(0,j) = F(0,j-1) +F(0,j);
②非边界。这种情况下，F(i,j)从它的左路径和上路径中选择最小的那个，再加上自己的一个便可。
F(i,j) = min(F(i-1,j),F(i,j-1))+F(i,j);
初始化：除了两种边界情况，对于F(0,0)本身就自己这个值。
返回结果：F(row-1,col-1)。走到最后，就是最小权值的和了。
代码如下：
int minPathSum(vector<vector<int> >& grid) { // write code here const int M = grid.size(); const int N = grid[0].size(); //全部初始化为0 vector<vector<int>> ret(M,vector<int>(N,0)); //初始化F(0)(0) ret[0][0] = grid[0][0]; //初始化F(0,i)和F(i,0) for(int i = 1;i!= M ;++i) { ret[i][0] = ret[i-1][0]+grid[i][0]; } for(int i = 1;i != N ;++i) { ret[0][i] = ret[0][i-1]+grid[0][i]; } for(int i = 1;i!=M;++i) { for(int j = 1;j!=N;++j) { ret[i][j] = min(ret[i-1][j],ret[i][j-1])+grid[i][j]; } } int result = ret[M-1][N-1]; return result; }
