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

爱被打了一巴掌 2022-10-29 09:13 185阅读 0赞

### 典例 ###

#### [70. 爬楼梯][70.] ####

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
    输出： 2
    解释： 有两种方法可以爬到楼顶。
    
    1.  1 阶 + 1 阶
    2.  2 阶

示例 2：

输入： 3
    输出： 3
    解释： 有三种方法可以爬到楼顶。
    
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶

**题解**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70][]

class Solution { 
        int[] cache = null;
    
        public int climbStairs(int n) { 
            cache = new int[n + 1];
            return func(n);
        }
    
        int func(int n){ 
            int res = 0;
            if((res = cache[n]) != 0){ 
                return res;
            }
    
            if(n == 1){ 
                res = 1 ;
            }else if(n == 2){ 
                res = 2;
            }else{ 
                res = func(n -1) + func(n -2);
            } 
    
            cache[n] = res;
            return res;
        }
    }

#### [120. 三角形最小路径和][120.] ####

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
    输出：11
    解释：如下面简图所示：
       2
      3 4
     6 5 7
    4 1 8 3
    自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
    输出：-10

**法一：记忆化搜索**

*  递归程序编写核心：明确**递归树每个节点的含义**，该含义也是每次递归入参，且也会根据这个条件判断终止情况
    
     *  例如 fb 的递归树，每个节点的含义是 n
        
        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1][]
     *  例如 mergeSort ，每个节点的含义是 size
        
        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2][]
     *  例如 这道题，每个节点的含义是 层次和在层次中的索引
 *  明确**递归要从递归树的根节点开始**
    
     *  递归树每个节点的操作是：**直接继续递归获得子节点的值，然后跟自己的值进行操作**

class Solution { 
        // 注意：这里是一个优化，不使用 map 作为 cache ，使用数组
        Integer[][] cache;
    
        public int minimumTotal(List<List<Integer>> triangle) { 
            cache = new Integer[triangle.size()][triangle.size()];
            return func(triangle , 0 ,0);
        }
    
        int func(List<List<Integer>> triangle , int level , int idx){ 
            Integer res = null;
            if((res = cache[level][idx]) != null){ 
                return res;
            }
    
            if(level == triangle.size() - 1){ 
                res = triangle.get(level).get(idx);
            }else{ 
                int l = func(triangle , level + 1, idx);
                int r = func(triangle , level + 1, idx + 1);
                res = triangle.get(level).get(idx) + Math.min(l, r);
            }
    
            cache[level][idx] = res;
            return res;
        }
    }

**法二：动态规划**

*  由自顶向下的搜索，变为自底向上的递推
 *  和上面那个 dfs 深搜没有本质区别，深搜也是搜到底然后向上反馈

class Solution { 
        public int minimumTotal(List<List<Integer>> triangle) { 
            int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
            for(int i = triangle.size() - 1; i >= 0  ; i --){ 
                for(int j = 0 ; j < triangle.get(i).size() ; j ++){ 
                    dp[i][j] = Math.min(dp[i + 1][j] , dp[i + 1][j + 1]) + triangle.get(i).get(j);
                }
            }
    
            return dp[0][0];
        }
    }

#### [64. 最小路径和][64.] ####

给定一个包含非负整数的 `*m* x *n*` 网格 `grid` ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：** 每次只能向下或者向右移动一步。

**题解**

*  核心：
    
     *  还是上面说的要清楚递归树，明白每个递归节点的含义
     *  对于可达性说明：只要递归树可达，那么一定可达（因为递归树也代表着路径，并且每个子节点的返回值已经代表了从这个节点下去时，路径的最值）
 *  注意边界
    
     *  要避免 Math.min 会选中不可达的

class Solution { 
    
        Integer[][] cache = null;
    
        public int minPathSum(int[][] grid) { 
            cache = new Integer[grid.length][grid[0].length];
            return dfs(grid , 0 , 0);
        }
    
        int dfs(int[][] grid , int level , int idx){ 
            if(level == grid.length || idx == grid[level].length){ 
                return Integer.MAX_VALUE;
            }
            
            Integer res = 0;
            if((res = cache[level][idx]) != null){ 
                return res;
            }
    
            int l = dfs(grid , level + 1 , idx);
            int r = dfs(grid , level , idx + 1);
    
            if(level == grid.length - 1 && idx == grid[level].length - 1){ 
                res = grid[level][idx];
            }else{ 
                res = grid[level][idx] + Math.min(l , r);
            } 
    
            cache[level][idx] = res;
            return res;
        }
    }

#### [343. 整数拆分][343.] ####

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

**题解**

*  要弄清当前状态可以转移到多少种不同状态
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3][]

class Solution { 
        int[] cache = null;
        public int integerBreak(int n) { 
            cache = new int[n + 1];
            return dfs(n);
        }
    
        int dfs(int n){ 
            if(cache[n] != 0){ 
                return cache[n];
            }
    
            int max = 1;
            for(int i = 1 ; i < n ; i ++){ 
                int res = dfs(i);
                res = Math.max(res, i);
                max = Math.max(max , res * (n - i));
            }
    
            cache[n] = max;
            return max;
        }
    
    }

#### [279. 完全平方数][279.] ####

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

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

示例 1：

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

示例 2：

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

提示：

`1 <= n <= 104`

**题解**

class Solution { 
        int[] cache = null;
        public int numSquares(int n) { 
            cache = new int[n + 1];
            return dfs(n);
        }
    
        int dfs(int n){ 
            if(cache[n] != 0){ 
                return cache[n];
            }
    
            int min = Integer.MAX_VALUE;
            for(int i = 1 ; i <=100 ; i ++){ 
                int now = i * i;
                if(n == now){ 
                    min = 1;
                    break;
                }
                if( n - now < 1 ){ 
                    break;
                }
                min = Math.min(min , dfs(n - now) + 1);
            }
    
            cache[n] = min;
            return min;
        }
    }

[70.]: https://leetcode-cn.com/problems/climbing-stairs/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221024/7d0682daba1c4886a6e5e0af7dfdd8cb.png
[120.]: https://leetcode-cn.com/problems/triangle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221024/7d89e940e1a14176ad5f29f0ba55ee63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2]: /images/20221024/78519ffd98d04b06979eb611a8d0e695.png
[64.]: https://leetcode-cn.com/problems/minimum-path-sum/
[343.]: https://leetcode-cn.com/problems/integer-break/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]: /images/20221024/f2866758add2426b97fc5454cbdba605.png
[279.]: https://leetcode-cn.com/problems/perfect-squares/