如何识别动态规划？

求最值问题，因为动态规划原本就是最优化理论的一部分
一个问题有最优子结构和重叠子问题，注意，重叠子问题中，重叠的含义是一个dp[.]的值可能在未来计算更大问题时被用到，而不是必须要子问题的解是大问题的解的一部分，虽然某个地方的dp[.]值会被算到，但他并不一定就是解，而是要用这些dp[.]值来找到真正的最值

动态规划的三个部分

P1216 [IOI 1994] 数字三角形 Number Triangles

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大权值。

第一个行一个正整数 $r$ ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

单独的一行,包含那个可能得到的最大的和。

【数据范围】
对于 $100\%$ 的数据，$1\le r \le 1000$，所有输入在 $[0,100]$ 范围内。

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1