第 19 关 | 经典刷题思想之动态规划 2.白银挑战

动态规划是一个非常重要的问题，相关的题目也特别多，这里我们就一起学习几个难度适用的题目

关卡名	掌握动态规划如何解题的	我会了✔️
内容	1.最少硬币数问题	✔️
	2.最长连续递增子序列问题	✔️
	3.最长递增子序列问题	✔️
	4.最少完全平方数问题	✔️
	5.再论青蛙跳问题	✔️
	6.解法方法	✔️
	7.路径中的障碍物问题	✔️
	8.滚动数组处理技巧	✔️

本文我们就来盘点那些常见的动态规划问题，本章除了最后两个题，其他都使用一维数组就可以了，因此我们每道题都要先明白，这个基表arr的含义是什么，如何更新的：

本章，我们首先通过详细的过程一步步来分析最少硬币数的问题，仔细观察每一步都是在做什么。代码如何从比较low的样子优化到比较合理。从2.2开始我们的讲解会更加精简。

1. 最少硬币数

LeetCode322.给你一个整数数组 coins ，表示不同面额的硬币，以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

示例1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例2：
输入：coins = [2,5, 7], amount = 27
输出：3 
解释：21 = 7 + 7 + 7

画图分析

这个题，其实使用上一章的回溯法也能做，问题就是效率太低了。假如coins = [2,5, 7], amount = 27，在求解过程中，每个位置都可以从{2,5,7}中选择，因此可以逐步将所有情况枚举出来，然后再找到要求的最少硬币数，图示如下：

通过上面的图，我们发现f[20]等已经存在多次重复计算了，这就是存在大量的重复计算问题，效率低，所以可以使用动态规划来优化。

另外貌似贪心也可以，直觉告诉我们尽量使用大的，例如假如要求的是27，此时应该先连续用7 + 7+7=21，最后的6没法了就用2，则就是3个7加3个2，一共6个，但我们可以这么做7+5+5+5+5=27 ，使用5枚硬币就够了，这就是贪心的思路，但对于本题就是错误的。

使用动态规划能同时满足效率和准确性的最佳，自然地，我们设状态f(x)=最少用f(x)枚硬币能拼出x。对应到上面基表就表示最少用arr[i]个硬币能表示出i来。我们先看上面给的示例1的情况：

上面图中，索引表示的是amount，而每个位置表示就是最少需要arr[i]个硬币就能拼出来。但是有些场景下可能不能将所有位置都能拼接出来的，例如示例2中的：

我们注意上面有些位是放的是M，表示的就是不能拼出来的意思。接下来我们就以coins={2,5,7}来详细分析如何一步步实现DP。
第一步：确定状态和子问题

什么是状态？前面介绍过，解动态规划的时候需要一个数组，状态就是这个数组的每个元素f[i]表示什么。

DP从思想上看仍然是递归，我们要找到将问题范围缩小的递推表达式，也就是状态转移方程。对于大部分DP的题目，先看最后一步的情况更容易分析出来，所以我们的武功心法第一条是从后向前找递归。

这里的最后一步就是：虽然我们不知道最优策略是什么，但是我知道最后得到最优策略一定是K枚硬币，a1，a2，...ak，而且面值加起来是27，而除掉ak这枚硬币，前面硬币加起来就是27-ak。此时我们得到:

这里貌似我们还不知道ak是多少？但是那一枚一定是2，5，7中的一个。

如果ak是2，那么f(27)应该是f(27-2)+1,加上最后这一枚硬币2。 f(25)+1
如果ak是5，那么f(27)应该是f(27-5)+1,加上最后这一枚硬币5。 f(22)+1
如果ak是7，那么f(27)应该是f(27-7)+1,加上最后这一枚硬币7。 f(20)+1

除此之外，没有其他可能了。那我们最后到底要使用哪一个呢？很简单，就是选上面三种情况最小的那个，也就是：

f(n):n是我们是要拼的数，这里f(n) 表示拼成n所需的最少硬币数

f(27)= min{ f(25)+1,f(22)+1,f(20)+1}

f(27)= min{ f(25),f(22),f(20)}+1

f(n)=min{f(n-2),f(n-5),f(n-7)}+1

f(27)=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}

在上面的过程中，我们不关心前面的K-1枚硬币是怎么拼出27-ak的，前K-1步可能有一种拼法，也可能有100种，甚至我们也没确定ak和k是啥，但是能确定的是前面一定拼出了27-ak，并且此时使用的硬币总数m=k-1枚一定是最少的，否则就不是最优策略,这里本题的一个核心，也是不太好理解的地方。

到此，要处理的子问题就是”最少用多少枚硬币可以拼出27-ak，而原始问题是"最少用多少枚硬币拼出27"。这样，我们就将原问题转化成了一个子问题，而且规模更小27-ak。

而至于最后一个ak，我们就是简单枚举了一下，要么是2，要么是5，要么是7，这就是局部枚举。而且到现在为止，我们也不知道到底用哪一个，唯一能确定的就是最后一个肯定是从2,5,7中选了一个，所以只是得到这样一个壳子：

f(27)=min{f(25)+1,f(22)+1,f(20)+1}

那接下来要怎么办呢？很简单，就是根据递归的思想再去算f(25)、f(22)和f(20)，例如计算f(20)就是:

f(20)=min{f(18)+1,f(15)+1,f(13)+1}

到这里仍然是不知道结果的，那就继续算，例如计算f(13)就是：

f(13)=min{f(11)+1,f(8)+1,f(6)+1}

到这里还是不知道结果，那就继续算，例如计算f(6)就是：

f(6)=min{f(4)+1,f(1)+1,f(-1)+1}

到这里很明显就非常容易计算了。

通过上面的例子，我们终于明白为什么找递推要从右向左，而计算的时候要从左向后了。

当然这里很明显f(-1)不符合要求的，那就设置为正无穷就行了。f(1)=也是正无穷，而f(4)=2，所以f(6)=2+1=3，然后继续计算最大的，最后就得到我们想要的结果。
第二步：确定状态转移方程

子问题确定之后，状态转移方程就很容易了，为了简化定义，我们设状态为f(x)=最少使用多少枚硬币拼出X。根据上面的分析，这里的ak，只能是2，5或者7。而我们要求的最少硬币数，就是求下面三个的最小值：

这个就是状态转移方程，在上一步我们已经分析出来了。

再往后，就是采用一样的套路将f(25)、f(22)和f(20)一起交给后续递归过程继续算。
第三步：确定初始条件和边界

很明显，本题的初始条件是: f[0]=0

对于上面的公式，有两个问题如果x-2，x-5，x-7，小于0怎么办？如果不能拼出x，就定义f[x]为正无穷，例如f[-1]=f[-2]=...=正无穷，表示拼不出1来。思考一下，这里为什么不能初始化为0？

当然这里有一点要注意，我们上面不可达用的是M，而不是Integer.MAX，因为这样的公式溢出了：

f(6)=min{2,Integer.MAX+1,Integer.MAX+1,}

我们可以使用amount来代替Integer.MAX
第四步：按顺序计算

开始执行上面的f[x]计算公式，f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}

虽然推导我们是从后向前，但是计算我们一般是从前向后的，在第一步中已经解释过，我们的计算过程如下：

初始条件：f[0]=0

然后计算f[1],f[2],...f[27]

这样的好处是计算f[x]的时候，f[x-2],f[x-5],f[x-7]都已经计算到结果了，因此效率更高。

执行的结构图如下（f[x]表示最少用几个硬币和拼出X，无穷表示无法拼出）：

现在请你思考一下这里的数字是怎么逐步计算出来的。这里其实每一步计算都是尝试3种硬币，一共27步，但是与递归相比，没有任何重复计算。因此算法时间复杂度为27*3。而递归的时间复杂度远远大于该数。

在这里每一步都尝试三种硬币，一共27步，对应的也就是一维数组的大小。

可以看到，与递归相比没有任何重复计算，因此效率更高。
第五步：代码实现

经过上面的分析之后，我们接下来就要实现上面的逻辑。根据上面f[x]的公式，我们可以写出第一版的代码：

//不能执行,仅仅做学习思考
 int coinChange(int[] coins, int amount) {
        int max = amount + 1; Interge.MAX
        int[] dp = new int[amount + 1];
         Arrays.fill(dp, max);
         dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
          if(check(i,coins)){
            dp[i] = min(dp[i], dp[i - coins[0]] + 1,dp[i - coins[1]] + 1,dp[i - coins[2]] + 1);
          }   
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

 boolean check(int i,int []coins){
   // 这里要保证if里使用的i - coins[j]等大于零
   // 这里还要保证不越界，写起来比较复杂 ，我们理解功能即可 
}

上面的min()方法我们暂时不实现，反正是从中找最小的那个。但这个代码不太优雅，dp的计算太长了，我们可以通过下面的方式来调整一下：

//不能执行,仅仅做学习思考
public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
           dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
          if(check(i,coins) ){//简写
            dp[i] = min(dp[i], dp[i - coins[0]] + 1);
            dp[i] = min(dp[i], dp[i - coins[1]] + 1);
            dp[i] = min(dp[i], dp[i - coins[2]] + 1);
          }   
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
 boolean check(int i,int []coins){
   // 这里要保证if里使用的i - coins[j]等大于零
   // 这里还要保证不越界，写起来比较复杂 ，我们理解功能即可 
}

这样我们就可以通过三次计算dp分别来处理coins[]数组的情况。但是这么写仍然不好，如果coins[]数组比较大，if判断就会非常长。怎么办呢？好办，加个循环来解决。

最终代码如下：

public static int coinChange(int[] coins, int M) {
        int max = M + 1;
        int[] dp = new int[M + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= M; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[M] > M ? -1 : dp[M];
    }

 def coinChange(self, coins, amount) :
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

int coinChange(vector<int>& coins, int M) {
    int max = M + 1;
    int dp[max];
    fill(dp, dp + max, max);
    dp[0] = 0;
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j < coins.size(); j++) {
            if (coins[j] <= i) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    if (dp[M] > M) {
        return -1;
    }
    return dp[M];
}

这就是本题最终的实现方法。

这里虽然是递归，但是是通过循环+数组来实现的，这就是为了消除冗余加速计算。
总结

我们现在来总结一下求最值型DP的步骤：

1.确定状态和子问题，从最后一步开始（最优策略中使用的最后一枚硬币ak）推导f(n)与子问题之间的关系，然后将其化成子问题(最少的硬币拼出更小的面值27-ak)。

2.通过状态，我们可以得到状态转移方程：f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}

3.处理初始条件和边界情况。f[0]=0,其他的如果不能拼出来就标记为f[X]=正无穷。

4.从小到大开始计算。这里就是从f[0]、f[1]、f[2]..向后计算。

2. 最长连续递增子序列

LeetCode674.给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7]也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。

对于本题，不用动态规划也可以解决，例如我们前面介绍的《滑动窗口》就可以。如果使用动态规划的话，我们仍然先手动画一下，看看数组变成什么样子：

很明显就是从前向后累计一下，如果不再是递增了，就将f[x]设置为1，然后继续向前走。

这种问题也称为序列型动态规划，给定一个序列或者网格，需要找到序列中某个/些子序列或者网格中的某条路径，要求满足某种性质最大/最小，求计数或者判断存在性问题。
第一步：确定状态和子问题

分析最后一步，对于最优策略，一定有最后一个元素a[j]。我们先考虑简单情况：

第一种情况：最优策略中最长连续上升子序列就是{a[j]}，答案是1。
第二种情况：子序列长度大于1，那么最优策略中a[j]前一个元素肯定是a[j-1]，这种情况一定是a[j-1]<a[j]的。

因为是最优策略，那么它选中的以a[j-1]结尾的连续上升子序列一定是最长的。

这里我们也得到了子问题：求以a[j-1]结尾的最长连续上升子序列，而本来是求以a[j]结尾的最长连续上升子序列。

状态：设f[j]=以a[j]结尾的最长连续上升子序列的长度。

则转移方程就是：

注意上图中红色线前面的是表达式，后面是要满足的条件。
第二步：初始条件和边界

情况2必须满足：j>0,即a[j]前面至少还有一个元素并且a[j]>a[j-1]满足单调性。
第四步：按照顺序计算

计算f[0]，f[1]，f[2]，...，f[n-1]

和硬币组合题不一样的是，最终答案不一定是f[n-1]，因为我们不知道最优策略中最后一个元素是哪个a[j]。所以答案是max{f[0]，f[1]，f[2]，...，f[n-1]}。

public   int findLengthOfLCIS(int[] nums) {
     int[] dp = new int[nums.length];
     for (int i = 0; i < dp.length; i++) {
         dp[i] = 1;
     }
     int res = 1;
     for (int i = 0; i < nums.length - 1; i++) {
          if (nums[i + 1] > nums[i]) {
              dp[i + 1] = dp[i] + 1;
          }
         res = res > dp[i + 1] ? res : dp[i + 1];
        }
     return res;
}

def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        result = 1
        dp = [1] * len(nums)
        for i in range(len(nums)-1):
            if nums[i+1] > nums[i]: #连续记录
                dp[i+1] = dp[i] + 1
            result = max(result, dp[i+1])
        return result

 int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int result = 1;
        vector<int> dp(nums.size() ,1);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) { // 连续记录
                dp[i] = dp[i - 1] + 1;
            }
            if (dp[i] > result) result = dp[i];
        }
        return result;
    }

3. 最长递增子序列

LeetCode300.给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例1：
输入：nums = [10,9,2,5,3,7,101,1]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为4。

注意本题与上一题的区别就是没说一定是连续的，例如上面示例里2和7就不是连续的。本题该怎么做呢？我们还是先手动算一下看看：

我们看一下使用DP解决问题的方法：
第一步：确定状态

最后一步：对于最优的策略，一定有最后一个元素a[j]。

第一种情况：最优策略中最长上升子序列就是{a[j]}，答案是1。

第二种情况：子序列长度大于1，那么最优策略中a[j]前一个元素是a[i]，并且a[i]<a[j]

第二种情况：子序列长度大于1，那么最优策略中a[j]前一个元素是a[i]，并且a[i]<a[j]

因为是最优策略，那么它选中的以a[i]结尾的上升子序列一定是最长的。

所以我们就得到子问题：因为不确定最优策略中a[j]前一个元素a[i]是哪一个，需要枚举每个i，求以a[j]结尾的最长上升子序列。化为子问题：i<j

状态：设f[j]=以a[j]结尾的最长上升子序列的长度

第三步：初始条件和边界情况

情况2必须满足：①i>=0;② a[j]>a[i]，也就是满足单调性。
第四步：计算顺序

计算f[0]、f[1]、f[2]、....f[n-1]，答案就是这些数中最大的那个。

本题的时间复杂度为O(n^2)，空间复杂度O(n)。

public int lengthOfLIS(int[] A) {
      int n=A.length;
      if(n==0){
          return 0;
      }
      int []f=new int[n];
      int i,j,res=0;
      for(j=0;j<n;j++){
          f[j]=1;
          for(i=0;i<j;i++){
              if(A[i]<A[j]&&f[i]+1>f[j]){
                  f[j]=f[i]+1;
              }
          }
          res=Math.max(res,f[j]);
      }
      return res;
    }

def lengthOfLIS(self, nums):
    if not nums:
        return 0
    dp = []
    for i in range(len(nums)):
        dp.append(1)
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

int lengthOfLIS(vector<int>& A) {
    int n = A.size();
    if (n == 0) {
        return 0;
    }
    int f[n];
    int i, j, res = 0;
    for (j = 0; j < n; j++) {
        f[j] = 1;
        for (i = 0; i < j; i++) {
            if (A[i] < A[j] && f[i] + 1 > f[j]) {
                f[j] = f[i] + 1;
            }
        }
        res = max(res, f[j]);
    }
    return res + 1;
}

4. 最少完全平方数

LeetCode279.给你一个整数 n ，返回和为n的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例1：
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例2：
输入：n = 13
输出：2
解释：13 = 4 + 9
 4 + 9
 4 4 4 1
 4 4 1 1 1 1 1 1
 4 1 1 1 1 1 1 1 1 1

这个题如果通过暴力来算，一定会超时，我们还是考虑如何通过DP来做。首先我们看一下手动画一下看看数组的变化：

第一步：确定状态

先看序列的最后一步：关注最优策略中最后一个完全平方数j^2，那么最后策略中n-j^2也一定被划分成最少的完全平方数之和。因此需要知道n-j^2最少被分成几个完全平方数之和，而原问题是求n最少被分成接完全而平方数之和，这就是子问题。

根据子问题，我们可以确定状态了：设f[i]表示i最少被分成几个完全平方数之和。
第二步：确定状态转移方程

设f[i]表示i最少被分成几个完全平方数之和。

第三步：确定初始条件和边界条件

初始条件：0被分成0个完全平方数之和。f[0]=0。

然后依次计算f[1],...，f[N]

答案就是f[N]。

public int numSquares(int n) {
        int[] f = new int[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                if (f[i - j * j] + 1 < f[i]) {
                    f[i] = f[i - j * j] + 1;
                }
            }
        }
        return f[n];
    }

def numSquares(n):
    f = [0] * (n+1)
    f[0] = 0
    for i in range(1, n+1):
        f[i] = sys.maxsize
        for j in range(1, int(i**0.5)+1):
            if f[i-j**2] + 1 < f[i]:
                f[i] = f[i-j**2] + 1
    return f[n]

int numSquares(int n) {
    int f[n + 1];
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = 10000;
        for (int j = 1; j * j <= i; j++) {
            if (f[i - j * j] + 1 < f[i]) {
                f[i] = f[i - j * j] + 1;
            }
        }
    }
    return f[n];
}

5. 再论青蛙跳

LeetCode55.跳跃游戏，给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位part置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例2：
输入：nums = [3,2,1,0,4]
输出：false

本题也是个典型的贪心问题，我们在贪心章节重点介绍过，我们现在从动态规划的角度考虑如何解决。
第一步：确定状态

最后一步：如果青蛙能跳到最后一块石头n-1，我们考虑它跳的最后一步，这一步是从石头i跳过来的，i<n-1。

这需要同时满足两个条件：青蛙可以跳到石头i；最后一步不超过跳跃的最大距离：n-1-i<ai;
第二步：确定状态转移方程

那么我们需要知道青蛙能不能跳到石头i(i<n-1)，而原始问题是我们要求青蛙能不能跳到石头n-1，这就是子问题。

状态：设f[j]表示青蛙能不能跳到石头j(注意这里的f[j]是布尔类型)。因此可以确定状态转移方程了：

这里使用or是因为只要存在一个就可以了。

第三步：确定初始条件和边界情况

设f[j]表示青蛙能不能跳到石头j。

初始条件：f[0]=true，因为青蛙一开始就在石头0。
第四步：按顺序计算

根据第二步中定义的f[j]和状态转移方程，并根据第三步的初始条件开始计算f[1],f[2],....f[n-1]。

f[n-1]就是我们最终想要的结果：

public  boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return false;
        }
        int n = A.length;
        boolean[] f = new boolean[n];
        f[0] = true;
        for (int j = 1; j < n; j++) {
            f[j] = false;
            for (int i = 0; i < j; i++) {
                if (f[i] && (i + A[i] >= j)) {
                    f[j] = true;
                }
            }
        }
        return f[n - 1];
 }

def canJump(A):
    n = len(A)
    f = [False] * n
    f[0] = True
    for j in range(1, n):
        for i in range(j):
            if f[i] and (i + A[i] >= j):
                f[j] = True
    return f[n - 1]

bool canJump(vector<int>& A) {
    if (A.empty() || A.size() == 0) {
        return false;
    }
    int n = A.size();
    bool f[n];
    f[0] = true;
    for (int j = 1; j < n; j++) {
        f[j] = false;
        for (int i = 0; i < j; i++) {
            if (f[i] && (i + A[i] >= j)) {
                f[j] = true;
            }
        }
    }
    return f[n - 1];
}

对于本题我们其实就是从i位置开始一直测试i+A[i]能不能到达A[n-1]，因此本质上就是一个两次循环，因此时间复杂度是O(N^2)，空间复杂度为O(N)。

6. 解码方法

LeetCode91.解码方法：一条包含字母 A-Z 的消息通过以下映射进行了编码：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)"KJF" ，将消息分组为 (11 10 6)注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。

示例1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 

示例3：
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

本题第一感觉是个回溯问题，本题用回溯是可以的，问题仍然是容易超时，我们还是考虑一下DP怎么解决。
第一步：确定状态

解密成为字母串，最后一定有最后一个字母，A、B..或Z，这个字母加密时变成1、2、....、26.

所以最后一个字母要么单独用了，要么和前面一个一起使用，假如说单独使用，例如下面这样子：

假如此时有100中解密方式。而如果将最后两个一起使用，也就是下面这样子：

假如此时有50种方法，那么总共方法就是100+50=150。

这样我们就得到了子问题：设数字串长度为N ，要求数字串前N个字符的解密方式数，此时需要知道数字串前面N-1和N-2字符的解密方式数。

所以本题的状态就是：设字符串S前i个数字解密成字母串有f[i]种方式。
第二步：确定状态转移方程

设数字S前i个数字解密成字母串有f[i]种方式，

第三步：确定初始条件和边界情况

初始条件f[0]=1，即空串有1种方式解密，解密成空串就行了。

边界情况：如果i=1，只看最后一个数字就行了。
第四步：按照顺序计算

f[0]，f[1]，f[2]，....,f[N]，答案就是f[N]

public static int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && (check(s, i))) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }

    public static boolean check(String s, int i) {
        if (s.charAt(i - 2) == '0') {
            return false;
        }
        if ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') > 26) {
            return false;
        }
        return true;
    }

def numDecodings(s):
    n = len(s)
    f = [0] * (n + 1)
    f[0] = 1
    for i in range(1, n + 1):
        if s[i - 1] != '0':
            f[i] += f[i - 1]
        if i > 1 and check(s, i):
            f[i] += f[i - 2]
    return f[n]

def check(s, i):
    if s[i - 2] == '0':
        return False
    if (int(s[i - 2]) * 10 + int(s[i - 1])) > 26:
        return False
    return True

int numDecodings(string s) {
    int n = s.length();
    vector<int> f(n + 1, 0);
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] != '0') {
            f[i] += f[i - 1];
        }
        if (i > 1 && check(s, i)) {
            f[i] += f[i - 2];
        }
    }
    return f[n];
}

bool check(string s, int i) {
    if (s[i - 2] == '0') {
        return false;
    }
    int num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
    if (num > 26) {
        return false;
    }
    return true;
}

7. 路径中存在障碍物

我们在上面路径部分介绍了多种路径的问题，但是本专题还有个重要的拓展问题，就是假如网格中存在障碍物该怎么办。我们这里补充一下。

本题是在leetcode 62题要求的基础上，如果中间某个位置存在障碍物，那一共有多少种路径。假如在上面的网格中存在一个障碍物，你该怎么处理呢？

示例1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

这个处理方法不算复杂，假如没有障碍物的格子标记为0，有障碍物的标记为1，那么执行的时候如果当前位置dp[i][j]==1时，直接跳过就行了。这么写：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] dp = new int[m];
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[m - 1];
    }

def uniquePathsWithObstacles(obstacleGrid):
    n, m = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0] * m
    dp[0] = obstacleGrid[0][0] == 0 and 1 or 0
    for i in range(n):
        for j in range(m):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0
                continue
            if j - 1 >= 0 and obstacleGrid[i][j - 1] == 0:
                dp[j] += dp[j - 1]
    return dp[m - 1]

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int n = obstacleGrid.size();
    int m = obstacleGrid[0].size();
    vector<int> dp(m);
    dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
                continue;
            }
            if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[m - 1];
}

如果面试直接考63题，估计我们会崩溃，但是如果我们先将62题研究清楚了，63题是不是就很简单了？

面试算法最喜欢的是换换条件不断折腾，那这里我们能否再当一次面试官，假如有k个障碍物，k<min(m,n)，该怎处理呢？

其实，从代码的角度，我们什么都不用干，上面的代码就能执行，因为问题的关键在于传入进来的obstacleGrid数组包含多个元素1罢了，我们在双层循环里的这个判断足以处理。

if (obstacleGrid[i][j] == 1) {
      dp[j] = 0;
       continue;
 }

这也是我们一直说的，一个方法可以解决大量的问题。一个问题改改条件就能造出大量的题目，我们后面还会继续折腾！

8. 滚动数组技巧

我们前面介绍了很多滚动数组的问题，本小节通过杨辉三角再来学习一种使用滚动数组的技巧。

杨辉三角是一种很出名的三角形，它的特点是每个元素都是其二维矩阵中左上方和右上方的元素之和，是一种对称结构，如下所示：

在LeetCode中对应118和119两道题，不同之处，一个是打印整个三角形，第二个是只需要打印出最后一行就行了。我们现在重点研究一下只打印最后一行的情况。

显然这个用二维数组比较可行，为了方便实现我们将其结构可以稍作改变，也就是：

观察上面的图，我们可以得到几个结论:

1.每一行最右侧和最左侧都是1。

2.前两行都是1，从第三行才开始有累加的问题。也就是这里的2，之后每行的元素仍然满足是其左上角+右上角元素之和。

3.每一行的元素数量都与其行数一样，所以可以为第N行建立一个大小为N的数组。

此时就可以写出如下的代码：

public class Yanghui {
    public static void main(String args[]) {
        //确定一个有10个数组（元素为数组）的二维数组
        int a[][] = new int[10][];
        //取出a[0],a[1]......a[9]十个数组
        for (int i = 0; i < a.length; i++) {
            //为10个数组确定空间（元素数目）
            a[i] = new int[i + 1];
            //将所有数组的第一个和最后一个元素元素赋值为1
            a[i][0] = 1;
            a[i][i] = 1;
        }

        //取出a[0],a[1]......a[9]十个数组
        for (int i = 0; i < a.length; i++) {

            //从第三个数组开始
            if (i > 1) {
                for (int j = 0; j < a.length; j++) {

           //所有数组的第二个到倒数第二个元素，它们的值为前一个数组所对应的元素和前一个元素的和
           //（a[2][1]=a[1][1]+a[1][0])
                    if (j > 0 && j < i) {
                        a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
                    }
                }
            }
        }
        //通过下标访问数组的元素
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                //这里使用print不进行自动换行，使用“\t”进行跳格（tab key即为空格键)
                System.out.print(a[i][j] + "\t");
            }
            //这里每进行一次for循环，都将结果进行换行
            System.out.println();
        }
    }
}

如果要得到最后一行，我们只要将二维数组的最后一行打印一下就可以了。

那如果要求只能使用O(n)空间实现，该怎么做呢？很显然我们可以使用上面提到的滚动数组来做，但是这里最大的问题是在二维数组的计算公式：

arr[i][j]=arr[i-1][j-1]+arr[i-1][j]

在计算dp[i]的时候，还需要上一轮的dp[i-1]，但是这个值已经被覆盖了，如下图所示标记的几个位置以及后序位置都是这样子。

例如图中的“3”号位置，我们需要使用上一轮的2和当前位置1相加，可惜如果只使用一个dp[i]数组的时候，这里的2已经被覆盖成3了。后面标记的6和4等等都是类似的情况，因此仅仅靠一个一维数组无法解决问题。

那怎么办呢？简单！使用两个数组，也是O(n)空间，使用两个数组来轮流交换，其中黑色表示上一轮的结构。红色表示当前轮要更新的结果。从下面图示可以清楚看到如何执行的。

对于网格上的动态规划，如果f[i][j]只依赖与本行的f[i][x]与前一行的f[i-1][y]那么就可以采用滚动数组来节省空间

public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> cur = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return pre;
    }

def get_row(row_index):
    pre = []
    cur = []
    for i in range(row_index + 1):
        cur = []
        for j in range(i + 1):
            if j == 0 or j == i:
                cur.append(1)
            else:
                cur.append(pre[j - 1] + pre[j])
        pre = cur
    return pre

vector<int> getRow(int rowIndex) {
    vector<int> pre;
    for (int i = 0; i <= rowIndex; ++i) {
        vector<int> cur;
        for (int j = 0; j <= i; ++j) {
            if (j == 0 || j == i) {
                cur.push_back(1);
            } else {
                cur.push_back(pre[j - 1] + pre[j]);
            }
        }
        pre = cur;
    }
    return pre;
}

这种通过两个数组来实现空间优化的技巧在一些DP问题中经常使用，这里请同学们务必理解清楚。

如果说这里就是让你使用一个一维数组来完成，该怎么做呢？其实非常简单，观察上面的图我们会发现，当前行第 i 项的计算只与上一行第 i−1 项及第 i 项有关。因此我们可以倒着计算当前行，这样计算到第 i 项时，第i−1 项仍然是上一行的值。

验证一下执行是否有问题

public class Yanghui {
    public static  List<Integer> generate(int rowIndex) {
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add(0);
            for (int j = i; j > 0; --j) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }

    public static void main(String[] args) {
        List<Integer> yanghui = generate(6);
        for (int i = 0; i < yanghui.size(); i++) {
            System.out.print(yanghui.get(i) + " ");
        }
    }
}

class Yanghui:
   def generate(self,row_index):
    row = [1]
    for i in range(1, row_index + 1):
        row.append(0)
        for j in range(i):
            row[j] += row[j-1]
    return row

 

# 创建一个 Yanghui 对象并调用方法
yanghui = Yanghui()
print(yanghui.generate(6))

vector<int> generate(int rowIndex) {
        vector<int> row;
        row.push_back(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.push_back(0);
            for (int j = i; j > 0; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
}

int main() {
 vector<int> yanghui = generate(6);
        for (int i = 0; i < yanghui.size(); i++) {
            cout << yanghui[i] << " ";
        }
        cout << endl;
}

输出结果为：
1 6 15 20 15 6 1

第 19 关 | 经典刷题思想之动态规划 2.白银挑战—动态规划高频问题-灵析社区