例题
数塔（数字三角形）
输入n，表示输入n行数字组成的数字三角形，对于第i行，有i个数字， 求（1，1）到底边上的一条路径，要求使该路经上数字之和最大
样例如下：
输入：
5
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5‘
输出：max = 15；
#include<cstdio> #include<algorithm> using namespace std; int n, sav[1005][1005] = {}; long long dp[1005][1005] = {}; int main() { scanf("%d", &n); for(int i = 1;i <= n;i++) { for(int j = 1;j <= i;j++) { scanf("%d", &sav[i][j]); } } dp[1][1] = sav[1][1]; for(int i = 2;i <= n;i++) { for(int j = 1;j <= i + 1;j++) { dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]) + sav[i][j]; } } int ans = 0; for(int i = 1;i <= n;i++) { if(dp[n][i] >= ans) { ans = dp[n][i]; } } printf("max=%d", ans); return 0; }
dp的本质是在无后效性时，某一范围内最大值不受每一个小区间中所做选择的影响。
因此贪心思路基本都是不成立的（有的看起来能用贪心做，但是其实基本都有反数据）。
所以只能暴力模拟每一种情况（一定要考虑到所有情况才能解决问题）。
但是也有例外，即求每个小范围区间内的最优情况，再把所有小区间的最优情况合起来一起讨论，得到相对大一些的区间内的最优情况，最终得出全局最优解（这类题目基本都比较简单，可以少处理一些情况《没有讨论所有情况但是对所有可能最优的情况进行了充分的讨论，答案具有正确性》）。
而部分较为复杂的题目，例如将数字三角形这道题修改一下：
（1）增加负数
（2）求最大绝对值
（3）有负数，求最大值，并且给出一次清零当前累计值的机会、
我们就需要纬度不变，但是多加一个数组来存储更多需要用到的数据，有时还需要对例如第三问这样的特殊问题，讨论在每个位置清零带来的结果影响（即对于一些状态的转移，需要考虑所有的情况，但是对于其他的状态仍可用贪心优化的dp策略《即求区间最大值》）。
原文：https://www.cnblogs.com/mint-hexagram/p/14664198.html