开篇

我记得我之前有写过一点动态规划的文章，这两天刚好重新回顾了下 DP ，查阅的一些资料，再结合 Leetcode 的练习题，根据自己的理解，来重新认识一些动态规划。这篇文章的总体流程就是介绍动态规划的一些场景，解题思路，以及题目解析，我并不喜欢用一些专业的术语去介绍动态规划，这不是我的风格，而且我解释的也没有 Google 的好。

✏️动态规划的场景

我觉得动态规划是挺难理解的，可能就在于它的思想不符合正常人的思维方式。它的解题就像递归那样，已经不能按照人脑去一步步去追踪结果，然后返回了值，想想自己在学习递归的时候，有没有脑子里一直在想这个递归过程的调用，我这么干过！这一步应该交给计算机，而动态规划需要我们定义状态，然后推出状态转移方程，状态转移方程找到之后，其实题目也就解决一半了。

动态规划的一些场景，典型的比如求一些最大最小值，背包问题，爬楼梯......，下面从一个例子中慢慢去了解动态规划吧，从典型的爬楼梯开始吧。这篇文章涉及到的所有题目都是以动态规划的思想解题，并不是说这道题只能用动态规划来解，不存在的。

其实我们求 n 阶台阶的总走法和 n-1 阶台阶的总走法本质上一样的，也就是说这个问题可以被分解为包含最优子结构的子问题。求这个解是可以从它的子问题的解推导出来的。

1. 当 n =1 时，肯定只有一种走法，也就是向上走一步 (dp [1]=1)。当 n=2 时，两种走法 (dp [2]=2)，一种每一次走一步，两次到达，一种一次走两步一次到顶。

对于 n 层台阶，当前可以从两个位置上来:

2. 从第 n-1 的位置向上迈进一步

3. 从第 n-2 的位置向上迈进二步

从上面的第一点我们可以知道初始的状态，从第二第三点我们可以得出第 n 层台阶的总走法 = 它的下一层台阶的总走法 + 它的下下一层的台阶的总走法，为什么，因为到达当前层只有两种情况，要么从下一层跳一步，要么从下下一层跳两步。好了，这道题到这就已经解完了。你可能会问，那你刚说的动态规划呢？我说完了啊。上面的分析过程就是动态规划啊。就像我刚才说的，动态规划背后的思想简单概括就是，若要解一个指定的问题，我们需要解它的不同部分问题 (子问题)，再合并子问题求出最终想要的解。

因此，动态规划解题最重要的两个步骤:

1. 状态的定义 dp [1]=1，dp [2]=1

2. 状态转移的方程 dp [n]=dp [n-1]+dp [n-2]

这里的 dp[n] 表示的含义是当台阶为 n 时，总共有多少走种走法。就像上面说的， n 层台阶的总走法 = 它的下一层台阶的总走法 + 它的下下一层的台阶的总走法，我们并不需要关心 dp[n-1] 和 dp[n-2] 这个过程是如何推导出来的，我们只关心它的状态值。只要定义好了状态，找出状态转移方程，这个题目其实就已经解了一大半了。接下来实现一下具体的代码:

/**
     * @param Integer $n
     * @return Integer
     */
    function climbStairs($n) {
        if($n==1) return 1;
        $dp[1]=1;
        $dp[2]=2;
        for($i=3;$i<=$n;$i++){
            $dp[$i]=$dp[$i-1]+$dp[$i-2];
        }
        return $dp[$n];
    }

嗯，到这里。其实这道题也就解出来了，但是，千万别觉得动态规划就这点东西。这道题目只是入门级的题目，并不是什么复杂的场景，状态的定义以及状态转移方程相对来说易于推导出来。实际情况下，对于这两步的推导是有点难度的，有时候可能定义一维的状态还不够，需要二维 (接下来的题目会涉及到多维的)...... 说到这，其实动态规划的本质就是一个空间换时间的思想。但是请记住，动态规划解题思路最重要的两步就是状态的定义以及状态转移方程。动态规划区别于贪心算法的地方在于，它就像是获取了上帝的视角，每次能获取到全局的最优解，而不像贪心，每次得到是只是局部最优。单这一题过于无趣，接下来我会带上 Leecode 不同题型来认识动态规划，从简单到复杂题型。

Leetcode 120. 三角形最小路径和

这道题本身就是一个二维数组，所以我们再定义状态时候也定义一个二维数组 (先不考虑压缩空间)。$dp [$i][$j] 表示从底部到 (i,j) 位置最短路径和，初始的 dp 值就等于最后一排的值，同样的道理，这里定义的 dp[i][j] 的意思是从底部到达二维数组 (i,j) 的最小和。那么状态转移方程呢？从题目中可以看到这么一句话 每一步只能移动到下一行中相邻的结点上，对于我们这里，是从下往上计算，那么对应的状态转移方程:

当前 (i,j) 位置和的最小值： $dp [$i][$j]=$triangle [$i][$j]+min ($dp [$i+1][$j],$dp [$i+1][$j+1])

比如图中例子 5 那么它的 dp 转移方程即:$dp [2][1]= 它可以由下层的 $dp [3][1]+ 它自身 或者 下层的 $dp [3][2]+ 它自身值 哪个路径短，就是哪个。

请注意上面出现两个变量 $triangle[$i][$j] 以及 $dp[$i][$j] , 前者表示的是表中二维数组第 i 行 j 列上的值，而后者是我们定义的状态值表示在 (i,j) 这个位置上总和的最小值，它是由之前的一步步推导出来的。而这个推导的过程我们是不关心的，我们只关心它的结果。

为什么反着推呢，原因很简单，因为最后的值必然出现在 $dp [0][0] 的位置，顶层只有一个元素。

/**
     * @param Integer[][] $triangle
     * @return Integer
     */
    function minimumTotal($triangle)
    {
        if (empty(count($triangle))) {
            return 0;
        }
        for ($i = count($triangle) - 1; $i >= 0; $i--) {
            for ($j = 0; $j < count($triangle[$i]); ++$j) {
                $triangle[$i][$j] += min($triangle[$i + 1][$j], $triangle[$i + 1][$j + 1]);
            }
        }
        return $triangle[0][0];
    }

这里代码做了一点细微的处理，不需要额外定义 dp[]，因为我们在进入当前层计算最小和值的时候，只需要下一层最小和的状态值，而不是数组具体位置的值本身，所以每次算完可以覆盖原先的值，给上一层使用。

Leetcode 152. 乘积最大子序列

我们还是先按照之前说的先定义状态，然后求出状态转移方式。这道题用一个一维数组存储 dp 即可。

DP [i] 代表从下标 0 到下标 i 这个范围内的连续子数组最大的乘积

状态转移方程:

DP [i+1] = DP [i] * 当前下标的值

这里有个关键点在于 DP 保存的是当前位置连续子数组的最大的乘积，但是我们并不知道当前下标的值是负数还是正数，如果是负数，那么 DP[i+1] 将会是一个最小值，所以只是单纯的这样定义状态是不行的。如果是负数的话，我们就应该选取前面推出的负数最大值 即最小值。如果是正数的话我们才应该把之前的最大 DP 拿过来直接相乘，所以这里需要定义两个状态。最大值的状态 $max[$i] 和最小值的状态 $min[$i]。

/**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxProduct($nums)
    {
        $max[0] = $min[0] = $res = $nums[0];
        for ($i = 1; $i < count($nums); $i++) {
            $max[$i] = max($max[$i - 1] * $nums[$i], $min[$i - 1] * $nums[$i], $nums[$i]);
            $min[$i] = min($max[$i - 1] * $nums[$i], $min[$i - 1] * $nums[$i], $nums[$i]);
            $res     = max($res, $max[$i]);
        }
        return $res;
    }

如果觉得这样看着变扭，多定义两个变量作为中转。

/**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxProduct($nums)
    {
        $max = $min = $res = $nums[0];
        for ($i = 1; $i < count($nums); $i++) {
            $mx  = $max;
            $mn  = $min;
            $max = max(max($nums[$i], $nums[$i] * $mx), $nums[$i] * $mn);
            $min = min(min($nums[$i], $nums[$i] * $mx), $nums[$i] * $mn);
            $res = max($res, $max);
        }
        return $res;
    }