一、概念
DP定义
动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无
在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果
动态规划具备了以下三个特点
- 把原来的问题分解成了几个相似的子问题
- 所有的子问题都只需要解决一次
- 储存子问题的解
动态规划问题一般从以下四个角度考虑
- 状态定义
- 状态间的转移方程定义
- 状态的初始化
- 返回结果
动态规划的本质：对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)
状态定义的要求：定义的状态一定要形成递推关系
适用场景：最大值/最小值, 可不可行, 是不是，方案个数
二、Fibonacci
难度：Easy
状态：F(n)
状态转移方程：F(n) = F(n - 1) + F(n - 2)
初始值：F(1) = F(2) = 1
返回值：F(n)
#include <vector> class Solution { public: int Fibonacci(int n) { std::vector<int> v(40); v[1] = v[2] = 1; for(int i = 3;i <= n; ++i) { v[i] = v[i - 1] + v[i - 2]; } return v[n]; } };
上述解法的空间复杂度为O(n)
其实F(n)只与相邻的前两项有关，没有必要保存所有子问题的解，只保存两个子问题的解即可
下面方法的空间复杂度将为O(1)
class Solution { public: int Fibonacci(int n) { if(n == 1 || n == 2) return 1; int Fib1 = 1,Fib2 = 1; int ret = 0; for(int i = 3;i <= n; ++i) { ret = Fib1 + Fib2; Fib1 = Fib2; Fib2 = ret; } return ret; } };
三、字符串分割
难度：Medium
状态:
子状态：前1，2，3，...,n个字符能否根据词典中的词被成功分词
F(i)：前i个字符能否根据词典中的词被成功分词
状态递推:
F(i)：true{j < i && F(j) && substr[j+1,i]能在词典中找到} OR false
在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典中找到，则F(i)为true
初始值：F(0) = true
返回值：F(n)
#include <vector> #include <string> #include <unordered_set> using namespace std; 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); can_break[0] = true;//初始状态(辅助状态) for (int i = 1; i <= s.size(); ++i) { //j < i && F(j) && [j + 1, i] for (int j = 0; j < i; ++j) { if (can_break[j] && dict.find(s.substr(j, i - j)) != dict.end()) { can_break[i] = true; break; } } } return can_break[s.size()]; } };
四、三角矩阵
难度：Medium
方法一：正向推导
状态：
子状态：从(0,0)到(1,0),(1,1),(2,0),...(n,n)的最短路径和
F(i,j)：从(0,0)到(i,j)的最短路径和
状态转移方程：F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
初始值：F(0,0) = triangle[0][0]
返回结果：min(F(n-1, i))
#include <vector> using namespace std; class Solution { public: int minimumTotal(vector<vector<int> >& triangle) { if (triangle.empty()) return 0; int row = triangle.size(); for (int i = 1; i < row; ++i) { for (int j = 0; j <= i; ++j) { if (j == 0) triangle[i][j] = triangle[i - 1][j] + triangle[i][j];//左边界 else if (j == i) triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j];//右边界 else triangle[i][j] = min(triangle[i - 1][j], triangle[i - 1][j - 1]) + triangle[i][j]; } } int min_sum = triangle[row - 1][0]; for (int j = 1; j < row; ++j) { min_sum = min(min_sum, triangle[row - 1][j]); } return min_sum; } };
方法二：反向推导
状态：
子状态：从(n,n),(n,n-1),...(1,0),(1,1),(0,0)到最后一行的最短路径和
F(i,j)：从(i,j)到最后一行的最短路径和
状态转移方程：
F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]
初始值：
F(n-1,0) = triangle[n-1][0] F(n-1,1) = triangle[n-1][1]，...， F(n-1,n-1) = triangle[n-1][n-1]
返回结果：
F(0, 0)
这种逆向思维不需要考虑边界，也不需要最后寻找最小值，直接返回F(0,0)即可
#include <vector> using namespace std; class Solution { public: int minimumTotal(vector<vector<int> >& triangle) { int row = triangle.size(); for (int i = row - 2; i >= 0; --i) { for (int j = 0; j <= i; ++j) { triangle[i][j] = min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j]; } } return triangle[0][0]; } };
五、路径总数
难度：Easy
状态：
子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的路径数
F(i,j)：从(0,0)到达F(i,j)的路径数
状态递推：
F(i,j) = F(i-1,j) + F(i,j-1)
初始化：
特殊情况：第0行和第0列 F(0,i) = 1 F(i,0) = 1
返回结果：
F(m-1,n-1)
#include <vector> using namespace std; class Solution { public: int uniquePaths(int m, int n) { if (m < 1 || n < 1) return 0; vector<vector<int>> v(m, vector<int>(n, 1)); for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { v[i][j] = v[i - 1][j] + v[i][j - 1]; } } return v[m - 1][n - 1]; } };
