【LeetCode】动态规划问题：常见题型（下）

谁借莪１个温暖的怀抱￠ 2022-10-29 09:15 193阅读 0赞

### 典例 ###

#### [91. 解码方法][91.] ####

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

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

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“111” 可以将 “1” 中的每个 “1” 映射为 “A” ，从而得到 “AAA” ，或者可以将 “11” 和 “1”（分别为 “K” 和 “A” ）映射为 “KA” 。注意，“06” 不能映射为 “F” ，因为 “6” 和 “06” 不同。

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

题目数据保证答案肯定是一个 32 位 的整数。

示例 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" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例 4：

输入：s = "1"
    输出：1

**题解**

*  注意递归子节点的返回值含义（只有叶子节点返回 1 ，代表是一条路径，然后每个节点将所有其子节点的返回值加和起来，代表这个节点可以走的路径数）

class Solution { 
        int[] cache = null;
        public int numDecodings(String s) { 
            cache = new int[s.length() + 1];
            return dfs(s,0);
        }
    
        int dfs(String s , int startIdx){ 
            if(cache[startIdx] != 0){ 
                return cache[startIdx];
            }
    
            int sum = 0;
            for(int i = 1 ; i <= (startIdx <= s.length() - 2 ? 2 : startIdx <= s.length() - 1 ? 1 : 0 ); i ++){ 
                // 这里太耗时！
                String numString = s.substring(startIdx, startIdx + i);
                int num = Integer.parseInt(numString);
    
                if(num <= 26 && s.charAt(startIdx) != '0'){ 
                    int res = dfs(s , startIdx + i);
                    res = res == 0 ? startIdx + i >= s.length() ? 1 : 0 : res;
                    sum += res;
                }
            }
    
            cache[startIdx] = sum ;
            return sum;
        }
    }

#### [62. 不同路径][62.] ####

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
    输出：28

示例 2：

输入：m = 3, n = 2
    输出：3
    解释：
    从左上角开始，总共有 3 条路径可以到达右下角。
    
    1. 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
    输出：28

示例 4：

输入：m = 3, n = 3
    输出：6

**题解**

*  和上面那个路径题的区别是，这道题的有效路径是必须终止在目标节点，而上道题是只要把一条路径可以走完就可以

class Solution { 
        int[][] cache = null;
        
        public int uniquePaths(int m, int n) { 
            cache = new int[m][n];
            return dfs(m , n , 0 , 0);
        }
    
        int dfs(int xSize , int ySize , int x , int y){ 
            if( x >= xSize || y >= ySize){ 
                return 0;
            }
            
            if(cache[x][y] != 0){ 
                return cache[x][y];
            }
    
            int res;
            if( x == xSize - 1 && y == ySize - 1){ 
                res = 1;
            }else { 
                 res = dfs(xSize , ySize , x + 1 , y) + dfs(xSize , ySize , x , y + 1);
            }
    
            cache[x][y] = res;
            return res;
        }
    }

#### [63. 不同路径 II][63. _ II] ####

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 `1` 和 `0` 来表示。

**题解**

*  跟上个题无区别，返回 0 （也代表递归终止的情况）的可能多加了一个而已
 *  还是动态规划的老四步：
    
     *  1、确定递归树每个节点（即每个状态的含义）
     *  2、确定每个状态可以转移到哪几个状态，并且条件是什么
     *  3、确定每个节点返回值的含义
     *  4、确定每个节点对子节点返回值如何处理

class Solution { 
        int[][] cache = null;
    
        public int uniquePathsWithObstacles(int[][] obstacleGrid) { 
            cache = new int[obstacleGrid.length][obstacleGrid[0].length];
            return dfs(obstacleGrid, 0 , 0);
        }
    
        int dfs(int[][] obstacleGrid , int x, int y){ 
            if(x >= obstacleGrid.length || y >= obstacleGrid[0].length || obstacleGrid[x][y] == 1){ 
                return 0;
            }
            
             if(cache[x][y] != 0){ 
                return cache[x][y];
            }
    
            int res;
            if( x == obstacleGrid.length - 1 && y == obstacleGrid[0].length - 1){ 
                res = 1;
            }else { 
                 res = dfs(obstacleGrid , x + 1 , y) + dfs(obstacleGrid , x , y + 1);
            }
    
            cache[x][y] = res;
            return res;
        }
    }

#### [198. 打家劫舍][198.] ####

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
    输出：4
    解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
         偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
    输出：12
    解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
         偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

0 <= nums.length <= 100
    0 <= nums[i] <= 400

**题解**

class Solution { 
        int[] cache = null;
        public int rob(int[] nums) { 
            cache = new int[nums.length];
            for(int i =0 ; i < cache.length ; i ++) 
                cache[i] = -1;
            return dfs(nums , 0);
        }
    
        int dfs(int[] nums , int idx){ 
            if(idx >= nums.length){ 
                return 0;
            }
    
            if(cache[idx] != -1){ 
                return cache[idx];
            }
    
            int max = 0;
            for(int i = 0; i < (idx == nums.length - 1 ? 1 : 2)  ; i ++ ){ 
                max = Math.max(max , nums[idx + i] + dfs(nums , idx + i + 2));
            }
    
            cache[idx] = max;
            return max;
        }
    }

#### [213. 打家劫舍 II][213. _ II] ####

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
    输出：3
    解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
    输出：4
    解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
         偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [0]
    输出：0

提示：

1 <= nums.length <= 100
    0 <= nums[i] <= 1000

**题解**

*  和上个题不同的关键
    
     *  是否选了第一个元素，决定了是否可以选最后一个元素，所以 cache 对于选不选第一个元素不同（也就是说从选了第一个元素带来的状态转移，从转移到的这个节点开始下面的所有路径的节点是一个 cache）
     *  还存在一种情况，为了选最后一个，不选 idx 0，但也没选 idx 1（为了选 idx2），所以每个节点的状态转移就有三个了（选 idx、idx + 1、idx + 2）

class Solution { 
       int[][] cache = null;
        public int rob(int[] nums) { 
            cache = new int[2][nums.length];
            for(int i =0 ; i < nums.length ; i ++){ 
                cache[0][i] = -1;
                cache[1][i] = -1;
            }
            return dfs(nums , 0 , 0);
        }
    
        int dfs(int[] nums , int idx , int isRobZeroIndex){ 
            if(idx >= nums.length){ 
                return 0;
            }
    
            if(cache[isRobZeroIndex][idx] != -1){ 
                return cache[isRobZeroIndex][idx];
            }
    
            int max = 0;
            int nextStatus = nums.length - idx;
            nextStatus = nextStatus > 3 ? 3 : isRobZeroIndex == 1 ? nextStatus - 1 : nextStatus;
    
            for(int i = 0 ; i < nextStatus  ; i ++ ){ 
                if(idx == 0 && i == 0){ 
                    max = Math.max(max , nums[idx + i] + dfs(nums , idx + i + 2 , 1));
                    continue;
                }
                max = Math.max(max , nums[idx + i] + dfs(nums , idx + i + 2 , isRobZeroIndex));
            }
    
            cache[isRobZeroIndex][idx] = max;
            return max;
        }
    }

#### [309. 最佳买卖股票时机含冷冻期][309.] ####

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。  
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]
    输出: 3 
    解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

**题解**

*  核心：明确每个节点的含义与参数，有可能是两个参数才能代表一种状态（即一个节点）

class Solution { 
       int[][] cache;
        public int maxProfit(int[] prices) { 
            cache = new int[2][prices.length + 2];
            return dfs(prices , 0 , 0);
        }
    
        // status：当前天数状态，0（初始化状态）、1（买入）
        int dfs(int[] prices , int idx , int status){ 
            if(cache[status][idx] != 0){ 
                return cache[status][idx];
            }
    
            int max = 0;
            if(status == 0){  // 可以买入
                for(int i = 1 ; i <= prices.length - idx ; i ++){  // 不买入
                    max = Math.max(max , dfs(prices , idx + i , 0));
                }
                for(int i = 1 ; i <= prices.length - idx  ; i ++){  // 买入
                    max = Math.max(max , dfs(prices , idx + i, 1) - prices[idx]);
                }
            }else if(status == 1){  // 可以卖出
                for(int i = 1 ; i <= prices.length - idx  ; i ++ ){  // 不卖出
                    max = Math.max(max , dfs(prices , idx + i , 1));
                }
                for(int i = 1 ; i <= prices.length - idx  ; i ++){  // 卖出了
                    if(idx >= prices.length - 3){ 
                        return prices[idx];
                    }
                    max = Math.max(max , dfs(prices , idx + i + 1, 0) + prices[idx]);
                }
            }
    
            cache[status][idx] = max;
            return max;
        }
    
    }

**典例总结**

*  题目如果是求最优或者求路径，那么大概率是动态规划
 *  然后按照 状态（节点）含义 -> 下一个可转移状态，与转到该状态的条件 -> 对子节点返回值如果处理

[91.]: https://leetcode-cn.com/problems/decode-ways/
[62.]: https://leetcode-cn.com/problems/unique-paths/
[63. _ II]: https://leetcode-cn.com/problems/unique-paths-ii/
[198.]: https://leetcode-cn.com/problems/house-robber/
[213. _ II]: https://leetcode-cn.com/problems/house-robber-ii/
[309.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/