核心思想：拆分子问题，记住过往，减少重复计算。通过已知的问题，推导得出答案

那些忘记过去的人，注定要重蹈覆辙。——鲁迅

定义

动态规划是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果

基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式

基本术语

• 阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用 $k$ 表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。
• 状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。
• 无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
• 决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。
• 策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。（允许策略集合中达到最优效果的策略称为最优策略）
• 最优化原理：作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。（最优性原理实际上是要求问题的最优策略的子策略也是最优）

状态转移方程

给定 $k$ 阶段状态变量 $x(k)$ 的值后，如果这一阶段的决策变量一经确定，第 $k+1$ 阶段的状态变量 $x(k+1)$ 也就完全确定，即 $x(k+1)$ 的值随 $x(k)$ 和第 $k$ 阶段的决策 $u(k)$ 的值变化而变化，那么可以把这一关系看成 $(x(k)，u(k))$ 与 $x(k+1)$ 确定的对应关系，用 $x(k+1)=Tk(x(k),u(k))$ 表示。这是从 $k$ 阶段到 $k+1$ 阶段的状态转移规律，称为状态转移方程。

例

题目描述

有 $n$ 个城市，编号 $1$~$n$，有些城市之间有路相连，有些则没有，有路则会有一个距离。如图所示是一个含有 $11$ 个城市的交通图，连线上的数表示距离。现在规定只能从编号小的城市到编号大的城市。问：从编号为 $1$ 的城市到编号为 $n$ 的城市的最短距离是多少？

输入

第一行为 $n$，表示城市数，$n<=100$。

下面n行是一个 $n$*$n$c的邻接矩阵 $map[i,j]$，其中 $map[i,j]=0$ 表示城市 $i$ 和 $j$ 之间没有路相连，否则为两者之间的距离。

输出

输出一个数，表示最短距离，保证有解。

样例输入

11
0 5 3 0 0 0 0 0 0 0 0
5 0 0 1 6 3 0 0 0 0 0
3 0 0 0 8 0 4 0 0 0 0
0 1 0 0 0 0 0 5 6 0 0
0 6 8 0 0 0 0 5 0 0 0
0 3 0 0 0 0 0 0 0 8 0
0 0 4 0 0 0 0 0 0 3 0
0 0 0 5 5 0 0 0 0 0 3
0 0 0 6 0 0 0 0 0 0 4
0 0 0 0 0 8 3 0 0 0 3
0 0 0 0 0 0 0 3 4 3 0

样例输出

13

解

#include<cstdio>
#include<iostream>
#include<algorithm> 
using namespace std;
const int M=1<<30;//表示 2^30

int dp[105],a[105][105];
int main(void){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	fill(dp+2,dp+n+1,M);//按类型空间赋初值 等效于 for(int i=2;i<=n;i++) dp[i]=M;
	//memset();//按字节赋初值 
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i][j]!=0) dp[i]=min(dp[i],dp[j]+a[i][j]);
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}

或

#include<cstdio>
#include<iostream>
#include<algorithm> 
using namespace std;
const int M=1<<30;

int dp[105],a[105][105];
int main(void){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	fill(dp+2,dp+n+1,M);
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i][j]!=0) dp[j]=min(dp[j],dp[i]+a[i][j]);
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}

题目详情 - 数字三角形 - 战码少年-战码青少年编程（专业信息学奥赛编程训练） (qucode.cn)

#include<bits/stdc++.h>
using namespace std;

int a[105][105],ans;
int main(void){
	int n;
	cin>>n; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
			a[i][j]=max(a[i][j]+a[i-1][j-1],a[i][j]+a[i-1][j]);
			ans=max(ans,a[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}