文/菜鸟网络 - 镇予

​

先来看看动态规划的官方定义：

• 动态规划是运筹学的一个分支，是求解决策过程最优化的过程。（by百度百科）
• 动态规划算法是对每个子子问题只求解一次，将其结果存放在一张表中，从而避免每次遇到各个子问题时重新计算答案。（by算法导论）

前置条件

• 最优化原理： 一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质（袁平波，顾为兵，尹东编．数据结构及应用算法：中国科学技术大学出版社，2013-09）
• 无后效性： 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

我的见解

通过一个dp数组来储存计算的中间状态，从而避免重复计算。（重叠子问题）

基本概念

下面通过一个栗子🌰来引出动态规划的基本概念： 现在足够多的有1元，2元，5元硬币，需要凑n元，求所用的最少硬币数。 假设现在n为10099，作图分析如下所示：

从图中可以发现，发现了 dp[10097]被重复计算了两次，当数字更小时，被重复计算当次数更多。如果用一个备忘录数组来记录的话，就可以避免重复计算，这就是动态规划算法能提高计算效率的核心，以空间换时间。 因此，可以定义一维数组dp来储存计算当中间状态，其中dp(i)就表示凑i元所用最少的硬币数量。这就是备忘录。 dp = [f(0), f(1), ...,f(10097),…] 其中f(0)是表示当是初始状态。 从图中可以得到dp[10099] = min(dp[10098] , dp[10097] ,dp[10094]) + 1 可以推到出： f(n) = Math.min(f(n-1])， f(n-2)，f(n-5)) + 1 上式就是动态规划中当状态转移方程。 有一句话总结当很好，就是动态规划DP = 递归加缓存。 ​

难点

动态规划当难点主要体现在下面两个方面：

• 怎么加缓存？ => DP数组的维度，状态 ？
• 怎么求递归？=> 状态转移方程的求解

特别是求解状态转移方程，这个没有固化的公式，只能根据对于问题的分析求得。 ​

动态规划四步走

动态规划类的题目可以按照以下四个步骤来求解：

1. 定义缓存dp
2. 初始状态
3. 状态转移方程
4. 从dp缓存中获取结果

​

LeetCode 实例

分析过程

首先画图分析示例1，如下图所示：

之后考虑在12后加一个数字X，X取0的时候很特殊，因为0不能转码成任何一个字母，只能和前面的数字组合，如下图所示。

这个时候X前面的2就不具有代表性，因此考虑将2转换成字母P。 ​

当X=0就有以下两种情况

• 当P是1或2的时候，才能和X=0时组合成10或20。
• 当那个P>2时，PX肯定不能转码成字母，直接返回0。

当X不等于0时，也有以下两种情况：

• P等于0，则X不能和P结合，此时1PX和1P的结果相同
• P不等于0，又细分为以下两种情况：
  1. PX > 26, 则PX不能转码成字母，只能拆分，此时1PX的结果和1的结果时一样的
  2. PX小于等于26时，此时P和X可以单独转码，1PX的结果和1P相同；或者PX组合一起转码，此时1PX和结果和1的结果相同。

具体分析过程如下图所示：

套用四步走方法

第一步：定义缓存dp

定义一维数字dp ，第 i 个元素dp[i]表示从第一个字符到第i个字符的解码数。 ​

第二步：初始状态

若输入不为空，且第一个字符不为0，则dp[i]=1,否则直接返回0

第三步：状态转移方程

根据上面的分析图，总结如下：

第四步：从dp缓存中获取结果

dp数组的最后一项就是所求问题的解。 ​

示例代码

var numDecodings = function (s) {
  // dp[i]表示第i个字符的所有可能
  const list = s.split('');
  if (list.length === 0 || list[0] === '0') {
    return 0;
  }
  const dp = [];
  dp[0] = 1;
  for (let i = 1; i < list.length; i++) {
    const curChar = list[i];
    if (curChar === '0') {
      if (['1', '2'].includes(list[i - 1])) {
        dp[i] = i >= 2 ? dp[i - 2] : 1;
      } else {
        return 0;
      }
    } else {
      if (list[i - 1] === '0') {
        dp[i] = dp[i - 1];
      } else {
        const number = Number(list[i - 1]) * 10 + Number(list[i]);
        if (number <= 26) {
          dp[i] = i >= 2 ? dp[i - 1] + dp[i - 2] : 2;
        } else {
          dp[i] = dp[i - 1];
        }
      }
    }
  }
  console.log(dp);
  return dp.pop();
}

​

总结

动态规划问题实际上还是需要一定的经验积累，有点类似于建模的过程，需要通过不断的联系积累经验，总结一下几点：

1. f(n)是否和f(n-1),…,f(0)之间是否存在关联关系
2. 遍历过程中能够定义一个备忘录来减少重复计算
3. 记住四步走套路

其中1和2点是用于快速的判断是否可以使用动态规划是思想来解决遇到的实际问题。3点是解决动态规划问题的模版，需要记住。 ​

---