1、 什么样的问题适合用动态规划来求解
1.1. 问题具有最优子结构；就是说问题的最优解所包含的子问题的解也是最优的；比如数字三角形问题中对于第i行j列的元素来说，其到i+1行的最优路径是确定的即：max(dp[i+1][j], dp[i+1][j+1])。
1.2. 状态具有无后效性；即当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种路径演变到当前的这若干个状态，没有关系。
2、 动态规划问题解题的一般思路
1、将原问题分解为子问题
- 把原问题分解为若干个子问题，子问题和原问题形式类似，只是规模变小，子问题都解决了的话，原问题也就解决了；
- 子问题的解一旦求出就会被保存，所以每个子问题只用求解一次；
- 比如数字三角形问题中某个元素对应的最优路径的最大和就是一个子问题；
2、确定状态
- 将和子问题相关的各变量的一组取值，称为一个“状态”；一个状态对应于一个或多个子问题，所谓某个状态下的值，就是这个状态所对应的子问题的解；所有状态的集合就构成了问题的状态空间，状态空间的大小，与动规解决问题的时间复杂度相关；
- 比如数字三角形问题中每个元素对应的最优路径的最大和就是一个状态，总共有N*(N+1)/2个状态，乘以每个状态计算所需的时间就是整个问题的求解时间；
3、确定边界状态值
- 比如数字三角形问题中边界值就是三角形底边的值；
4、确定状态转移方程
- 如何从一个或多个值已知的状态，求出另一个状态的值，（“人人为我”递推型）。状态的转移可以用递推公式表示，此公式就叫状态转移方程；
- 比如数字三角形问题中的状态转移方程：
if(start_raw == n-1)//边界条件
max_sum[start_raw][start_col] = nums[start_raw][start_col];
else
int max_1 = maxSum(nums, start_raw + 1, start_col, n);
int max_2 = maxSum(nums, start_raw + 1, start_col + 1, n);
int max = max_1 >= max_2 ? max_1 : max_2;
max_sum[start_raw][start_col] = max + nums[start_raw][start_col];
3 实例讲解
例题一、 数字三角形
题目描述：
如下图所示的数字三角形图，寻找从顶至底的某处的一条路径，使该路径所经过的数字之和最大。（1）每一步只能沿左斜线向下或右斜线向下，只需要给出最大和就可以了，不必给出具体路径（2）1 < 三角形行数 < 101（3）三角形数字为0，1，…99
image.png
解法方法分析：
- 首先构建输入：该数据是三角形，属于二维图形，适合使用二维向量或是数组来表示；
可以使用如下代码来实现
#include<iostream>
#include<vector>
using namespace std;
void getInput(vector<vector<int> >& dp_test)
{
vector<vector<int> > dp_test;
cout << "enter raw num: " << endl;
int raw_n;
cin >> raw_n;
int input;
for(int raw = 0; raw < raw_n; raw++)
{
vector<int> temp_vector;
for(int col = 0; col < raw+1; col++)
{
cout << "enter the numbers" << endl;
cin >> input;
temp_vector.push_back(input);
}
dp_test.push_back(temp_vector);
}
cout << "The raw num is: " << raw_n << endl;
cout << "The input nums are: " << endl;
for(size_t i = 0; i < dp_test.size(); I++)
{
for(size_t j = 0; j < dp_test[i].size(); j++)
{
cout << dp_test[i][j] << " ";
}
cout << endl;
}
}
得到的数组是这样的
The raw num is: 5
The input nums are:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
这里元素dp[i][j], i和j从0开始，每次向下移动的路径就是dp[i+1][j]或者dp[i+1][j+1];maxSum(i,j)表示从dp[i][j]到底边的各条路径中，最佳路径的数字和；
- 解法一、 该问题是典型的递归问题
从dp[i][j]出发，下一步只能走dp[i+1][j]或者dp[i+1][j+1]，即只要知道maxSum(i+1,j)和maxSum(i+1,j+1)就能得到maxSum(i,j) = max(maxSum(i+1,j),maxSum(i+1,j+1)) + dp[i][j]；边界就是maxSum(n-1,*) = nums[n-1][*]
int maxSum(vector<vector<int>> nums, int start_raw, int start_col, int n)
{
if(start_raw == n-1)//边界条件
return nums[start_raw][start_col];
int max_1 = maxSum(nums, start_raw + 1, start_col, n);
int max_2 = maxSum(nums, start_raw + 1, start_col + 1, n);
int max = max_1 >= max_2 ? max_1 : max_2;
return max + nums[start_raw][start_col];
}
int main()
{
vector<vector<int>> input_vec;
getInput(input_vec);
cout << maxSum(input_vec, 0, 0, input_vec.size()) << endl;
return 0;
}
分析递归算法的时间复杂度，该递归方法是从上到下一层一层的递归求解，那么存在大量的重复计算，每个元素上面重复计算的次数如下入所示：
image.png
根据等比数列求和可该算法的时间复杂度是O(2^n),对于n=100行，时间肯定是超时的；
- 解法二、 记忆递归型动规程序，采用递归的方式，时间复杂度太大主要是因为优太多的重复计算，改进的方法是将计算出的每一个maxSum值都存起来，下次用到的时候直接取用，避免重复计算；那么这时的时间复杂度根据等差数列求和可以知道是O(n^2);
#include<iostream>
#include<vector>
using namespace std;
void getInput(vector<vector<int>>& dp_test, vector<vector<int>>& dp_max)
{
vector<vector<int> > dp_test;
cout << "enter raw num: " << endl;
int raw_n;
cin >> raw_n;
int input;
for(int raw = 0; raw < raw_n; raw++)
{
vector<int> temp_vector;
vector<int> max_vector;
for(int col = 0; col < raw+1; col++)
{
cout << "enter the numbers" << endl;
cin >> input;
temp_vector.push_back(input);
max_vector.push_back(-1);
}
dp_test.push_back(temp_vector);
dp_max.push_back(max_vector);
}
}
int maxSum(vector<vector<int>> nums, int start_raw, int start_col, int n, vector<vector<int>> max_sums)
{
if(max_sums[start_raw][start_col] != -1)
return max_sums[start_raw][start_raw];
if(start_raw == n-1)//边界条件
{
max_sums[start_raw][start_col] = nums[start_raw][start_raw];
}
else
{
int max_1 = maxSum(nums, start_raw + 1, start_col, n, max_sums);
int max_2 = maxSum(nums, start_raw + 1, start_col + 1, n, max_sums);
int max = max_1 >= max_2 ? max_1 : max_2;
max_sums[start_raw][start_col] = max + nums[start_raw][start_col];
}
}
int main()
{
vector<vector<int>> input_vec;
vector<vector<int>> max_vec;
getInput(input_vec,max_vec);
cout << maxSum(input_vec, 0, 0, input_vec.size(), max_vec) << endl;
return 0;
}
- 解法三、递推（“人人为我”递推型动归程序）
递归会有调用栈溢出的风险；可以使用递推的方式，即从最后一行开始，逐层向上求出每个元素位置的最大值，这样既可以每个元素只计算一次，时间复杂度为O(2^n),又不使用递归，不会有调用栈溢出的风险；采用递推时，最后一行的最大值就是自己，倒数第二行的最大值时元素本身加上最后一行两个数的最大值，上面的行以此类推，结果如下：
输入数据：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
递推后的结果：
| 30 | ||||
|---|---|---|---|---|
23 |
21 | |||
20 |
13 | 10 | ||
| 7 | 12 |
10 | 10 | |
| 4 | 5 |
2 | 6 | 5 |
上面的表格过程可以看出来，整个过程会从底向上求出每一个节点在以该节点开始到最下面的最优路径的解；这个值只是该节点的最优解，并不是该层的最优解，但是当我们以此方式求到最上面的节点即顶点时，顶点的最优解就是我门需要的最优解；这里不需要记录路径；
#include<iostream>
#include<vector>
using namespace std;
/*
@dp_max:的元素对于每一行都是复用的
*/
void getInput(vector<vector<int>>& dp_test, vector<int>& dp_max)
{
vector<vector<int> > dp_test;
cout << "enter raw num: " << endl;
int raw_n;
cin >> raw_n;
int input;
for(int raw = 0; raw < raw_n; raw++)
{
vector<int> temp_vector;
for(int col = 0; col < raw+1; col++)
{
cout << "enter the numbers" << endl;
cin >> input;
temp_vector.push_back(input);
}
dp_test.push_back(temp_vector);
for(auto iter : dp_test[raw_n - 1])
dp_max.push_back(iter);
}
}
int maxSum(vector<vector<int>> nums, int start_raw, int start_col, int n, vector<int> max_sums)
{
for(int raw = n - 1; raw > start_raw - 1; raw--)
{
for(int col = 0; col < n; col++)
{
int max = nums[raw + 1][col] >= nums[raw + 1][col+1] ? nums[raw + 1][col] : nums[raw + 1][col + 1];
max_sums[col] = max + nums[raw][col];
}
}
return max_sums[start_col];
}
int main()
{
vector<vector<int>> input_vec;
vector<int> max_vec;
getInput(input_vec,max_vec);
cout << maxSum(input_vec, 0, 0, input_vec.size(), max_vec) << endl;
return 0;
}
- 递归到动规程序的一般转换方法
- 递归函数有n个参数，就定义一个n维的数组，数组的下标是递归函数参数的取值范围，数组元素的值时递归函数的返回值，这样就可以从边界开始，逐步填充数组，这就相当于计算递归函数值的逆过程。
例题二、 最长公共子序列
题目描述：
给出两个字符串，求出这样的一 个最长的公共子序列的长度:子序列 中的每个字符都能在两个原串中找到， 而且每个字符的先后顺序和原串中的 先后顺序一致。
解法方法分析：
首先拿到题目，是求最优解的题目，一般用dp来解，但是dp需要有无后效性的最优子问题，这个需要好好设计dp的状态，设计不出来就不能用dp；
首先想到的是对于长度为m和n的两个字符串S1和S2，其
- 状态：最长公共子序列用
dp(m,n)表示； - 那么显然边界条件：
dp(i,0) = 0; (i = 0...m)
dp(0,j) = 0; (j = 0...n)
- 状态转移方程
当S1[i-1] == S2[j-1]时这时显然的：dp(i, j) = dp(i-1, j-1) + 1;
当S1[i-1] != S2[j-1]时有：dp(i, j) = max(dp(i-1,j), dp(i, j-1))
屏幕快照 2019-11-19 上午12.34.52的副本.png
- 显然dp(i, j)不会比dp(i-1,j)和dp(i, j-1)小；
- 那么会不会比两个都大呢？假设dp(i, j)比dp(i-1,j)大，因为二者唯一不同的就是S1[i-1]，那么S1[i-1]一定是S1和S2的最长公共子序列的最后一个元素；同理，假设dp(i, j)比dp(i,j-1)大，那么S2[j-1]一定是S1和S2的最长公共子序列的最后一个元素；那么必然S1[i-1] == S2[j-1]，而这个于假设冲突，所以可以得到上面的状态转移方程；
-
采用递推的方式实现
屏幕快照 2019-11-19 上午12.40.12.png
image.png
int longestCommonSubsequence(string text1, string text2) {
if(text1.size() == 0 || text2.size() == 0){
return 0;
}
int len1 = text1.size();
int len2 = text2.size();
vector<vector<int>> lcs;
lcs.resize(len1 + 1);
for(size_t i = 0; i <= len1; i++){
lcs[i].push_back(0);
lcs[i].resize(len2 + 1);
}
for(size_t j = 1; j <= len2; j++){
lcs[0][j] = 0;
}
for(size_t i = 1; i <= len1; i++){
for(size_t j = 1; j <= len2; j++){
if(text1[i-1] == text2[j-1]){
lcs[i][j] = lcs[i-1][j-1] + 1;
} else {
lcs[i][j] = lcs[i-1][j] > lcs[i][j-1] ? lcs[i-1][j] : lcs[i][j-1];
}
}
}
return lcs[len1][len2];
}
