动态规划是一种解决问题的指导思想。

一、例题

1. Triangle
   Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
   For example, given the following triangle
   [
   [2],
   [3,4],
   [6,5,7],
   [4,1,8,3]]
   The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
   NOTE:
   Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

二、分析

1. 根据题目，可采用深度优先搜索方法。

深度优先搜索中，类似于二叉树的递归算法，有两种策略： 遍历和分治。
1） 采用遍历 traverse, 把要变化的值（这里是sum）作为dfs递归函数的参数，在传递过程中使用。
这里dfs的定义是，走到当前下（x，y）这个点的和为sum，这个sum随着点的下移在变化，因此把sum作为dfs的一个参数。

// traverse
void dfs(int x, int y, int sum) {
    if (x == n) {
        if (sum < best) {
            best = sum;
        }
        return;
    }
    // 每次往下走有两个选择
    dfs(x + 1, y, sum + a[x][y]);  // 向正下方走
    dfs(x + 1, y + 1, sum + a[x][y]);  // 向右下方走
}
dfs(0,0);

分析其复杂度：O(2^n)
本题中的三角形本质上是一个二维数组，数据结构如下图所示。

如果我们想要到达图中的节点 e ，经过的路径会有：a->b->e， a->c->e 两种。
同理，如果想要到达节点 i ，经过的路径会有：abei, acei, acfi 三种
可以看到，随着层的增加，到达每个节点的路径种类会逐渐增加，遍历的时间复杂度会随着层数增加迅速增加。
具体而言，从顶点出发，每个节点往下走会有两个选择，根据数学的排列知识，到达最底层，一共有2 * 2 * ... * 2 * 2 种到达底端的路径，其中有 n 个2。因此，总的时间复杂度为O(n * 2^n) = O(2^n)

<数据结构与算法>——动态规划入门（1）

原文：https://www.cnblogs.com/isguoqiang/p/11482132.html