[leetcode刷题]——动态规划

2023-12-23 23:35:27

此博客主要记录使用动态规划解题的方法

斐波那契数列

一、爬楼梯

70. 爬楼梯（easy） 2021-07-25

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

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

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

　　第一次见到这个人题的我，这不就递归嘛，然后就。。。。。。很快啊，超出时间限制

class Solution {
    public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

　　不使用递归，将每一次遍历使用变量存储下来。递归的时候重复运算太多，此方法解决了这个问题

class Solution {
    public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        int pre2 = 1, pre1 = 2;
        for(int i = 3; i <= n; i++){
            int cur = pre1 + pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

二、强盗抢劫

198. 打家劫舍（medium） 2021-07-25

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

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

　　比上一题稍微复杂一点，但是是一个套路

class Solution {
    public int rob(int[] nums) {
    int pre2 = 0, pre1 = 0;
    for (int i = 0; i < nums.length; i++) {
        int cur = Math.max(pre2 + nums[i], pre1);
        pre2 = pre1;
        pre1 = cur;
    }
    return pre1;
    }
}

三、强盗在环形街区抢劫

213. 打家劫舍Ⅱ （medium） 2021-07-25

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

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

//核心思想，将环形队列分成两个队列
//一个 0 - n-1, 一个 1 - n, 返回一个最大的
class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int len = nums.length;
        if(len == 1) return nums[0];
        return Math.max(robCalculate(nums,0,len - 2), 
                        robCalculate(nums,1,len - 1));
    }
    public int robCalculate(int[] nums, int first, int last){
        int pre2 = 0;
        int pre1 = 0;
        for(int i = first; i <= last; i++){
            int cur = Math.max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

矩阵路径

一、矩阵的最小路径和

64. 最小路径和（medium） 2021-07-25

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

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

　　惯性思维的我习惯使用回溯算法，可奈何递归的方法太容易溢出了。

　　递归已死，动态规划当立

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] path = new int[m][n];
        path[0][0] = grid[0][0];
        for(int i = 1; i < m; i++){
            path[i][0] = path[i - 1][0] + grid[i][0];
        }
        for(int j = 1; j < n; j++){
            path[0][j] = path[0][j - 1] + grid[0][j];
        }
        
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                path[i][j] = Math.min(path[i][j - 1], path[i - 1][j]) 
                    + grid[i][j];
            }
        }
        return path[m - 1][n - 1];
    }   
}

二、矩阵的总路径数

62. 不同路径（medium） 2021-07-25

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

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

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

　　想用数学方法降维打击，结果我被打击了，又溢出了。

class Solution {
    public int uniquePaths(int m, int n) {
        return factorial(m + n - 2) /(factorial(m - 1) * factorial(n - 1));
    }
    public int factorial(int k){
        if(k == 0 || k == 1) return 1;
        return factorial(k - 1) * k;
    }
}

　　换个方法，超过100%，嘻嘻

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

数组区间

一、数组区间和

303. 区域和检索 - 数组不可变（easy） 2021-07-26

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public int sumRange(int left, int right) {
        int ret = 0;
        for(int i = left; i <= right; i++){
            ret  += nums[i];
        }
        return ret;
    }
}

这个题的题目意思没有表达清楚，需要高频多次调用sumRange函数

正经答案是这样的

class NumArray {

    private int[] sums;

    public NumArray(int[] nums) {
        sums = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}

二、数组中等差递增子区间的个数

413. 等差数列的划分（medium） 2021-07-26

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的子数组个数。

子数组是数组中的一个连续序列。

这个题的主要解题思想就是，使用dp 数组记录以 nums[n]结尾的等差数组的个数，如果nums[n + 1]和前面的依然等差，那么dp[n+1] = dp[n]+1

/**
动态规划的题目最重要的是找到他的递归函数
*/
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 2; i < n; i++){
            if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]){
                dp[i] = dp[i - 1] + 1;
            }
        }
        int count = 0;
        for(int d : dp){
            count += d;
        }
        return count;
    }
}

分割整数

一、分割整数的最大乘积

343. 整数拆分（medium） 2021-07-26

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

　　动态规划最重要的找到递归的函数。

　　这个题的主要思路，dp[i] 表示整数 i 对应的最大乘积，那么 dp[i] = dp[j] * (i - j), j属于[1, i -1] ,然后遍历取最大值

　　dp[i] 的最大值不一定是 dp[i - j] * j, 还有一种可能是（i- j）* j 。这是多出来的一种组合。

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            for(int j = 1; j < i; j++){
                dp[i] = Math.max(dp[i], Math.max(dp[i-j] * j, (i-j)*j));
            }
        }
        return dp[n];
    }
}

二、按平方数来分割整数

279. 完全平方数（medium） 2021-07-27

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

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

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

　　找到动态规划中的递归方法尤其重要

class Solution {
    public int numSquares(int n) {
        List<Integer> list = square(n);
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++){
            int min = Integer.MAX_VALUE;
            for(int l : list){
                if(i - l < 0) break; 
                min = Math.min(min, dp[i - l] + 1);
            }
            dp[i] = min;
        }
        return dp[n];    
    }
    //返回小于n 的所有完全平方数
    public List<Integer> square(int n){
        List<Integer> list = new ArrayList<>();
        int diff = 3;
        int gap = 2;
        int i = 1;
        while(true){
            list.add(i);
            i += diff;
            diff += gap;
            if(i > n) break;
        }
        return list;
    }
}

三、分割整数构成字母字符串

91. 解码方法（medium） 2021-07-27

一条包含字母 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 ，请计算并返回解码方法的总数。

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

　　这个题没什么意思，和算法关系不大，主要是边界条件的判断。

public int numDecodings(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == ‘0‘ ? 0 : 1;
    for (int i = 2; i <= n; i++) {
        int one = Integer.valueOf(s.substring(i - 1, i));
        if (one != 0) {
            dp[i] += dp[i - 1];
        }
        if (s.charAt(i - 2) == ‘0‘) {
            continue;
        }
        int two = Integer.valueOf(s.substring(i - 2, i));
        if (two <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}

最长递增子序列

一、最长递增子序列

300. 最长递增子序列（medium） 2021-07-27

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

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

　　传统的动态规划套路，但是时间复杂度 O(N*2)，空间复杂度 O(N)。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        for(int i = 0; i < len; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i] ,dp[j] + 1);
                }
            }
        }
        int max = 0;
        for(int i = 0; i < len; i++){
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

　　有更好的二分查找的方法，时间复杂度为 O(NlogN)

二、一组整数对能够构成的最长链

646. 最长数对链（medium）2021-08-01

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

　　贪心算法解决

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                return o1[1] - o2[1];
            }
        });
        int len = 1;
        int last = pairs[0][1];
        for(int i = 1; i < pairs.length; i++){
            if(pairs[i][0] > last){
                last = pairs[i][1];
                
                len++;
            }
        }
        return len;
    }
}

　　这里使用动态规划反而并不是最佳的方案

public int findLongestChain(int[][] pairs) {
    if (pairs == null || pairs.length == 0) {
        return 0;
    }
    Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
    int n = pairs.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (pairs[j][1] < pairs[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Arrays.stream(dp).max().orElse(0);
}

三、最长摆动子序列

376. 摆动序列（medium） 2021-08-01

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为摆动序列的最长子序列的长度。

　　这个题并没有用到动态规划，使用数学规律时间复杂度达到 O(N)

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int up = 1, down = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[i - 1]){
                up = down + 1;
            }else if(nums[i] < nums[i - 1]){
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}

最长公共子序列

1143. 最长公共子序列（medium） 2021-08-01

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

　　值得注意的是，很容易走向动态规划就一个dp[] 一维数组的误区，这里用到的是二维数组。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int l1 = text1.length();
        int l2 = text2.length();
        int[][] dp = new int[l1  + 1][l2 + 1];
        for(int i = 1; i <= l1; i++){
            for(int j = 1; j <= l2; j++){
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[l1][l2];
    }
}

[leetcode刷题]——动态规划

码农公寓

斐波那契数列

一、 爬楼梯

70. 爬楼梯 （easy） 2021-07-25

二、强盗抢劫

198. 打家劫舍 （medium） 2021-07-25

三、 强盗在环形街区抢劫

213. 打家劫舍Ⅱ （medium） 2021-07-25

矩阵路径

一、矩阵的最小路径和

64. 最小路径和 （medium） 2021-07-25

二、矩阵的总路径数

62. 不同路径 （medium） 2021-07-25

数组区间

一、数组区间和

303. 区域和检索 - 数组不可变 （easy） 2021-07-26

二、数组中等差递增子区间的个数

413. 等差数列的划分 （medium） 2021-07-26

分割整数

一、分割整数的最大乘积

343. 整数拆分 （medium） 2021-07-26

二、按平方数来分割整数

279. 完全平方数 （medium） 2021-07-27

三、 分割整数构成字母字符串

91. 解码方法 （medium） 2021-07-27

最长递增子序列

一、 最长递增子序列

300. 最长递增子序列 （medium） 2021-07-27

二、 一组整数对能够构成的最长链

646. 最长数对链 （medium）2021-08-01

三、最长摆动子序列

376. 摆动序列 （medium） 2021-08-01

最长公共子序列

1143. 最长公共子序列 （medium） 2021-08-01

相关文章

一、爬楼梯

70. 爬楼梯（easy） 2021-07-25

198. 打家劫舍（medium） 2021-07-25

三、强盗在环形街区抢劫

64. 最小路径和（medium） 2021-07-25

62. 不同路径（medium） 2021-07-25

303. 区域和检索 - 数组不可变（easy） 2021-07-26

413. 等差数列的划分（medium） 2021-07-26

343. 整数拆分（medium） 2021-07-26

279. 完全平方数（medium） 2021-07-27

三、分割整数构成字母字符串

91. 解码方法（medium） 2021-07-27

一、最长递增子序列

300. 最长递增子序列（medium） 2021-07-27

二、一组整数对能够构成的最长链

646. 最长数对链（medium）2021-08-01

376. 摆动序列（medium） 2021-08-01

1143. 最长公共子序列（medium） 2021-08-01