动态规划
参考视频
引入
A -> D找最短路径。
使用深度优先搜索遍历固然可行，但是效率较低，因为存在很多重复计算。
（!为什么不使用广度优先搜素，因为广度优先搜索不计算权重，得到的结果只是步数最少的结果，只可用于无权图）
使用贪心算法也不对，在图中可以找出反例：
如果使用贪心算法，那么应该选择：A -> B2 -> C3 -> D，但是实际的最短路径是：A -> B2 -> C2 -> D。
到底如何解决？
我们可以将问题倒过来，记\(d(x)\)为从D到x的最短路径长度，从与D点相邻的开始，那么就有：
\(d(C1) = 4,d(C2) = 2,d(C3) = 5\)，继续下去，找这些点相邻的位置，就有：
\(d(B1) = 4+d(C2) = 6,d(B2) = 4+d(C2) = 6\)，最后找到A点，发现：
\(d(A) = 3+d(B2) = 9\)，所以最短路径是：A -> B2 -> C2 -> D，路长为9。
我们发现了规律，每一次做出选择的时候，假设当前的点是\(N\)，与它相连的点为\(M_1，M_2，M_3，...，M_n\)，那么：
\(d(N) = \min\{l(M_n) + d(M_n)\}\)①，其中\(l(M_n)\)表示从\(N\)到\(M_n\)的路长。
在这样的方法中，我们做的每一步选择是根据前面的选择决定的，同时也影响了后面的选择，这就是动态规划。每一步选择叫做一次状态转移，像①式的式子叫做状态转移方程。
数塔问题
我们可以使用二维数组存储这个数塔：
对照一些，对于一个其中的点\((x,y)\)，它的相邻为\((x+1,y)\)和\((x+1,y+1)\)。
我们可以像上面一样写出状态转移方程，这次把路径和最大值记为\(s(x)\),当前位置的值为t：
\(s(x,y) = t(x,y) + \min\{s(x+1,y),s(x+1,y+1)\}\)
我们要找的结果就是\(s(1,1)\)。
代码实现
#include <iostream>
using namespace std;int n;
int dp[102][102] = {0};
int map[102][102] = {0};int main(int argc, char const *argv[])
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> map[i][j];}}// 构建dp数组for (int i = n; i >= 1; i--){for (int j = 1; j <= i; j++){dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + map[i][j];}}cout << dp[1][1];return 0;
}