前置知识
递推、递归、搜索、贪心


目标
数字三角形问题
最长上升子序列问题
最长公共子序列问题
最大子段和问题


数字三角形问题
有一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字，……，第n层有n个数字。现在要从第一层走到第n层，每次只能选择左下方或者右下方的数字，

问：“最后将路径上所有数字相加后得到的和最大是多少？”

引导思考：

（1）从起点到第一行第一列的答案是固定的。

（2）在第一步骤基础上，从起点到第二行的答案也是固定的。

（3）在第三行时，7 有两种选择，显然会选择从累积更大的过来才是最优的
    若将f[i][j]定义为从第一行第一列到第 i 行第 j 列的路径上的数字和的最大值，
    则到 数字7 的递推式为：f[3][2] = max(f[2][1],f[2][2]) + 7
    
（4）可得出一般递推式为 f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j]
    我们只需要推到第n行，就可以得到ans = max{f[n][1…n]}
解法提炼：

（1）状态定义：
f[i][j]定义从第一行第一列到第 i 行第 j 列的路径上的数字和的最大值
    
（2）所求：
max{f[n][1…n]}

（3）状态转移：
f[i][j]=max(f[i-1][j-1],f[i-1][j]) + a[i][j]
示例代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int a[N][N], dp[N][N], n;

int main(){
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];

// 填表法
memset(dp, -0x3f, sizeof dp);
dp[1][1] = a[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++){
dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i][j]);
if (j > 1) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i][j]);
}

int ret = -2e9;
for (int j = 1; j <= n; j++) ret = max(ret, dp[n][j]);
cout << ret << '\n';

return 0;
}
最长上升子序列问题
给定一个长度为 n 的数字序列，求最长的上升子序列长度。

如3、1、2、6、4、5的最长上升子序列为1、2、4、5，故答案为4。
解法提炼

（1）状态定义：
    f[i] 定义为到第 i 个数字为止，
    且第 i 个数必须为该子序列的最后一个数字时，所获得的最长子序列的长度。
    
（2）所求：max{f[1…n]}
    
（3）状态转移：f[i] = max{f[j] + 1} | 1 <= j <= i-1, a[j] < a[i]。
示例代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int a[N], n;
int dp[N], ret;

int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];

// 填表法
a[0] = -2e9, dp[0] = 0;
for (int i = 1; i <= n; i++)             // 枚举以i为结尾
for (int j = 0; j < i; j++)          // 枚举从哪个数来
if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1); 

for (int i = 1; i <= n; i++) ret = max(ret, dp[i]);
cout << ret << '\n';

return 0;
}
最长公共子序列问题
给定两个长度为 n 的数字序列，求最长的公共子序列长度。

第一个数字序列为 1、6、2、5、4、7，
第二个数字序列为 1、2、5、5、2、7，

则最长的公共子序列为1、2、5、7，其长度为4。
解法提炼

（1）状态定义：
f[i][j] 定义为当第一行数字取到第 i 个，第二行数字取到第 j 个时，
    所能得到的最长子序列长度，
    且第 i 个数字和第 j 个数字不需要为所求子序列的最后一个数字（即这两个数字取到与否都可以）
    
（2）目标：f[n][n]
    
（3）状态转移：
f[i][j] = f[i-1][j-1] + 1           | a[i] = b[j] 
          max(f[i-1][j], f[i][j-1]) | a[i] ≠ b[j]

当 a[i] 与 b[j] 相等时，其会对目标值贡献 +1，
而 a[i] 与 b[j] 不相等时，显然这两个数字无法配对，

故对 f[i][j] 而言，a[i] 和 b[j] 中必有一个是多余的，
故 f[i][j] = max(f[i-1][j], f[i][j-1])

此时计算f[i][j]的时间复杂度为O(1)，故总的时间复杂度为O(n^2)。
最大子段和问题
Given an array of n numbers, our task is to calculate the maximum subarray sum.

//举例
-1 2 4 -3 5 2 -5 2

//最大子段和是10
2 4 -3 5 2
解法提炼

Consider the subproblem of finding the maximum-sum subarray that ends at position k. 
There are two possibilities:
1. The subarray only contains the element at position k.
2. The subarray consists of a subarray that ends at position k − 1,
   followed by the element at position k.

In the latter case, since we want to find a subarray with maximum sum, 
the subarray that ends at position k − 1 should also have the maximum sum. 
Thus, we can solve the problem efficiently by calculating 
the maximum subarray sum for each ending position from left to right.

int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
    sum = max(array[k],sum+array[k]);
    best = max(best,sum);
}
cout << best << "\n";
示例代码

#include <bits/stdc++.h>

using namespace std;

int a[20], n;
int dp[20];
int maxn = -0x3f3f3f3f;

int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];

for (int i = 1; i <= n; i++){
dp[i] = max(dp[i - 1], 0) + a[i];     //另起炉灶
maxn = max(maxn, dp[i]);    
}

cout << maxn << '\n';

return 0;
}


总结
动态规划是一个分水岭，很自然的就会认为这东西不好学，难倒了很多人
先从经典例题入手，模仿，照搬，照抄，这些方法统统用上，不必考虑什么创新，甚至什么理解
当这几个经典例题很流利的情况下，我们再进去理解动态规划的原理、专业术语
简单来讲，先学下去，再说