什么是动态规划？

       动态规划（Dynamic Programming）是通过组合子问题的解来解决问题的。动态规划是用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题。在求解的过程中通过子问题的解求出原问题的解。

       动态规划的分类：

1.       线性规划：拦截导弹，合唱队形，挖地雷等。

2.       区域规划：石子合并，加分二叉树，统计单词个数等。

3.       树形动规：贪吃的九头龙，二分查找树，聚会的欢乐等。

4.       背包问题：01背包问题，完全背包问题，分组背包问题，装箱问题，挤牛奶等

5.       除此之外还有插头DP，按位DP，状态压缩DP等等。

入门题目：数字三角形

题目描述：给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于

每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

       注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

       如：

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5

分析一下为什么不能使用贪心算法，即每一次走都走下一行的两个数值较大的。因为有可能在某一步的时候数值小没走到，但是该路径下面有较大的数值，就不会走到，就得不到最大的值。

1.朴素DFS搜索算法

可以采用朴素的深度优先搜索算法，即朴素DFS。每一次走都分为两步，第一步求出走下一步时走的最大值，然后加上此步的数值。

       完整的代码示例为：