【LeetCode】（动态规划ி）典型典中典，小白也秒懂✌

妖狐艹你老母 2023-01-11 12:00 142阅读 0赞

## 【LeetCode】（动态规划ி）典型典中典 ##

### 文章目录 ###

*   *  【LeetCode】（动态规划ி）典型典中典
     *   *  青蛙跳台阶问题★
         *  不同路径★★
         *  礼物的最大价值★★
         *  完全平方数★★
         *  组合总和IV★★
         *  零钱兑换★★
         *  分发糖果★★★
         *  最长上升子序列(LIS)★★
         *  最长公共子序列(LCS)★★

--------------------

### 青蛙跳台阶问题★ ###

[LeetCode 剑指 Offer 10- II. 青蛙跳台阶问题][LeetCode _ Offer 10- II.]

【**题目**】一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

【**示例**】

输入：n = 2
    输出：2

【**解题思路**】

斐波拉契数列 `f(n) = f(n - 1) + f(n - 2)`

class Solution {
        
        public int numWays(int n) {
        
            if(n < 2) return 1;
            long[] dp = new long[n + 1];
            dp[0] = dp[1] = 1;
            for(int i = 2; i <= n; i++) {
        
                dp[i] = dp[i - 1] + dp[i - 2];
                dp[i] %= 1000000007;
            }
            return (int)dp[n];
        }
    }

状态压缩版

class Solution {
        
        public int numWays(int n) {
        
            long f0 = 1,  f = 1;
            for(int i = 2; i <= n; i++) {
        
                long t = f;
                f = (f0 + f) % 1000000007;
                f0 = t;
            }
            return (int)f;
        }
    }

--------------------

### 不同路径★★ ###

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

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

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

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

【**示例**】

![在这里插入图片描述][20210126222801372.png_pic_center]

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

【解题思路】

**方法一**：动态规划

class Solution {
        
        public int uniquePaths(int m, int n) {
        
            int[][] dp = new int[101][101];
            for(int i = 0; i < m; ++i){
        
                dp[0][i] = 1;
            }
            for(int i = 0; i < n; ++i){
        
                dp[i][0] = 1;
            }
            for(int i = 1; i < n; ++i){
        
                for(int j = 1; j < m; ++j){
        
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[n - 1][m - 1];
        }
    }

**方法二**：数学组合问题

`(m + n)中选择m个`

class Solution {
        
        public int uniquePaths(int m, int n) {
        
            int C = m + n - 2;
            int K = (m < n ? m : n) - 1;
            double res = 1;
            for(int i = 1; i <= K; i++) {
        
                res = res * (C - i + 1) / i;
            }
            return (int)res;
        }
    }

--------------------

### 礼物的最大价值★★ ###

[剑指 Offer 47. 礼物的最大价值][Offer 47.]

【**题目**】在一个 m\*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

【**示例**】

输入: 
    [
      [1,3,1],
      [1,5,1],
      [4,2,1]
    ]
    输出: 12
    解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

【**解题思路**】

每次取左边或者上边最大值

class Solution {
        
        public int maxValue(int[][] grid) {
        
            int []dp = new int[grid[0].length + 1];
            for(int i = 1; i <= grid.length; i++){
        
                for(int j = 1; j <= grid[0].length; j++){
        
                    dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
                }
            }
            return dp[grid[0].length];
        }
    }

--------------------

### 完全平方数★★ ###

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

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

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

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

【**示例**】

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

【**解题思路**】

class Solution {
        
        public int numSquares(int n) {
        
            int[] dp = new int[n + 1];
            Arrays.fill(dp, n);
            dp[0] = 0;
            for(int i = 0; i <= n; i++) {
        
                for(int j = 1; j * j <= n; j++) {
        
                    if(i + j * j <= n) {
        
                        dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1);
                    }
                }
            }
            return dp[n];
        }
    }

--------------------

### 组合总和IV★★ ###

[LeetCode 377. 组合总和 Ⅳ][LeetCode 377. _]

【**题目**】给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

【**示例**】

nums = [1, 2, 3]
    target = 4
    所有可能的组合为：
    (1, 1, 1, 1)
    (1, 1, 2)
    (1, 2, 1)
    (1, 3)
    (2, 1, 1)
    (2, 2)
    (3, 1)
    请注意，顺序不同的序列被视作不同的组合。
    因此输出为 7。

【**解题思路**】

class Solution {
        
        public int combinationSum4(int[] nums, int target) {
        
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for(int i = 1; i <= target; i++){
        
                for(int j : nums){
        
                    if(i >= j){
        
                        dp[i] += dp[i - j];
                    }
                }
            }
            return dp[target];
        }
    }

--------------------

### 零钱兑换★★ ###

[LeetCode 322. 零钱兑换][LeetCode 322.]

【**题目**】给定不同面额的硬币 `coins` 和一个总金额 `amount`。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 `-1`。

你可以认为每种硬币的数量是无限的。

【**示例**】

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

【**解题思路**】

class Solution {
        
        public int coinChange(int[] coins, int amount) {
        
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, amount + 1);
            dp[0] = 0;
            for(int i = 1; i <= amount; i++) {
        
                for(int coin : coins) {
        
                    if(i >= coin) {
        
                        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                    }
                }
            }
            return dp[amount] > amount ? -1 : dp[amount];
        }
    }

--------------------

### 分发糖果★★★ ###

[LeetCode 135. 分发糖果][LeetCode 135.]

【**题目**】

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

*  每个孩子至少分配到 1 个糖果。
 *  评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

【**示例**】

输入：[1,0,2]
    输出：5
    解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

【**解题思路**】

从左向右遍历，若当前孩子评分高于左边的孩子，则比左边孩子多分一个苹果，否则分一个苹果；

从右向左遍历，若当前孩子评分高于右边的孩子且苹果数小于等于右边孩子，则比右边孩子多分一个苹果。此时，当前孩子以及他右侧的孩子苹果已经符合要求，可以累加求和。

class Solution {
        
        public int candy(int[] ratings) {
        
            if(ratings == null || ratings.length == 0) return 0;
            int n = ratings.length;
            int[] dp = new int[n];
            dp[0] = 1;
            for(int i = 1; i < n; i++) {
        
                if(ratings[i] > ratings[i - 1]) {
        
                    dp[i] = dp[i - 1] + 1;
                }else {
        
                    dp[i] = 1;
                }
            }
            int count = 0;
            for(int i = n - 1; i >= 0; i--) {
        
                if(i != n - 1 && ratings[i] > ratings[i + 1] && dp[i] <= dp[i + 1]) {
        
                    dp[i] = dp[i + 1] + 1;
                }
                count += dp[i];
            }
            return count;
        }
    }

--------------------

### 最长上升子序列(LIS)★★ ###

见往期力扣之最：[【LeetCode】（动态规划ி）力扣之最][LeetCode]

### 最长公共子序列(LCS)★★ ###

同见往期力扣之最：[【LeetCode】（动态规划ி）力扣之最][LeetCode]

[LeetCode _ Offer 10- II.]: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
[LeetCode 62.]: https://leetcode-cn.com/problems/unique-paths/
[20210126222801372.png_pic_center]: /images/20221119/b83ee969742149c29d884b6c468a1d54.png
[Offer 47.]: https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
[LeetCode 279.]: https://leetcode-cn.com/problems/perfect-squares/
[LeetCode 377. _]: https://leetcode-cn.com/problems/combination-sum-iv/
[LeetCode 322.]: https://leetcode-cn.com/problems/coin-change/
[LeetCode 135.]: https://leetcode-cn.com/problems/candy/
[LeetCode]: https://blog.csdn.net/weixin_44368437/article/details/113200020