一键难忘520

这个屌丝很懒，什么也没留下！

热门标签

Leetcode复盘9——动态规划_leetcode n x n 的方格里,每个格子里都放了一定数量的芝麻

作者：一键难忘520 | 2024-07-07 15:56:44

踩

leetcode n x n 的方格里,每个格子里都放了一定数量的芝麻

导读

动态规划作为面试高频的考点被大多数程序员所重视，本期就带来的是动态规划的一些基本题目以及解答思路，希望能对大家有所帮助

1.打家劫舍 / 强盗抢劫LeetCode198

难度：中等Medium
idea：
状态dp[i]：第[i]间房舍必偷获得的最高金额（注意此时第[i-1]间就不能偷了）
状态转移方程：取第[i-1]间必偷的最高金额和第[i-2]间必偷的最高金额加上偷当前房租的金额之间的较大值，即 $d p [i] = m a x (d p [i - 1], d p [i - 2] + n u m s [i])$

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int n = nums.length;                             // 保存一下长度,养成好习惯
        int[] dp = new int[n];                           // 建立一个和数组等长的dp数组
        
        // 赋初值
        dp[0] = nums[0];                                 // 若第[0]间房屋必偷,值为nums[0]
        dp[1] = Math.max(dp[0], nums[1]);            // 偷第[1]间,也可以写Math.max(nums[0],nums[1])
        
        for (int i = 2; i < n; i++) {                    // 因为[0]和[1]已经赋初值了,所以从[2]开始
            // 两种选择: 要么偷第[i-1]间,要么偷第[i-2]间和第[i]间
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);   // 滚雪球,原材料为上次和上上次的结果
        }
        return dp[n - 1];                                       // 返回dp数组的最后一个即可
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

改进版
因为状态推进的过程中只用到上一次和上上次的状态，故可以只定义两个整形变量prev和curr，分别存储后者dp[i-1] 和 前者dp[i-2]，其中prev代表前者dp[i-2]，curr代表后者dp[i-1]，其中后者下次还要接着用，就变成新前者了，即 $p r e v = c u r r — — （ 1 ）$ ，而新后者是由偷和不偷求出来的：
$c u r r = m a x (c u r r, p r e v + n u m s [i]) — — （ 2 ）$
其中等式左边的是新后者，右边的是旧前者和旧后者。
综合（1）（2）两式，我们可以先把旧后者存起来，等算完新后者之后把旧后者赋给新前者：
$temp = old\_curr,\\ new\_curr=max(old_curr,old\_prev+nums[i]),\\ new\_prev=temp,$
或者把旧前者存起来，先得到新前者，再用旧后者和旧前者计算新前者：
$temp = old\_prev,\\ new\_prev = old\_curr,\\ new\_curr=max(old\_curr,temp+nums[i]),$
逻辑是一样的，都行。

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev = 0;
        int curr = 0;

        // 循环整个数组
        for(int num : nums) {
            int temp = max(curr, prev + num);            // 先用temp把算出来的new_curr存起来,此时curr还是old_curr
            prev = curr;                                 // 先把old_curr赋给new_prev
            curr = temp;                                 // 再把上面计算好的new_curr给curr,这两句顺序不能反了
        }
        return curr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.打家劫舍 II / 强盗在环形街区抢劫LeetCode213

idea: 动态规划(DP method)
因为是环形的,所以处理状态转移关系的时候要小心些,分为两部分:
a. 若偷了第[0]间的房子,则第[n-1]间,即最后一间就不能偷了;
b. 若没偷第[0]间的房子,则第[n-1]间可以偷;
即调取上一题198打家劫舍的函数两次,取二者的较大值
状态dp[i]: 第[i]间必偷时所能得到的最大金额;
状态转移方程:
$d p [i] = M a t h . m a x (d p [i - 1], d p [i - 2] + n u m s [i])$
把原数组分成两部分，调用两次函数，最后取较大值
$m a x (h e l p e r (n u m s [1 :]), h e l p e r (n u m s [: - 1]))$

class Solution:
    def rob(self, nums: List[int]) -> int:
        # boundary case
        if not nums : return 0
        if len(nums) == 1: return nums[0]
        # 下面要调用该函数两次
        def helper(nums):
            if not nums : return 0
            if len(nums) == 1: return nums[0]
            n = len(nums)
            dp = [0] * n
            dp[0] = nums[0]
            dp[1] = max(dp[0], nums[1])
            for i in range(2, n):                           # i的范围: [2, n - 1]
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
            return dp[-1]                                   # 或返回dp[n-1]
        
        return max(helper(nums[1:]), helper(nums[:-1]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.最大子序和LeetCode53

idea: 动态规划(DP method)
状态dp[i]: 从nums[0]到nums[i]为止连续的若干个数的最大和,计算的原则就是看从nums[0]到nums[i-1]的最大和dp[i-1]
1.若dp[i-1]是负的,证明当前的数nums[i]没必要加上负数dp[i-1]让自己变小了,故弃之,只选nums[i];
2.若dp[i-1]是正的,则nums[i]可以加上一个正数让自己变得更大.
由于dp[i]只能代表从nums[0]到nums[i]的最大和,故它可能忽高忽低,所以要定义一个整型变量res存储历史最大和

e.g nums = [-2,1,-3,4,-1,2,1,-5,4]
dp[0] = -2;(没办法弃nums[0],只能取)
dp[1] = 1;(弃dp[0],只取nums[1])
dp[2] = -2(nums[2]=-3加上了1让自己变得更大了)
dp[3] = 4(弃dp[2],只取nums[3])
dp[4] = 3(nums[4]=-1加上dp[3]=4让自己变得更大了)
dp[5] = 5(nums[5]=2加上dp[4]=3让自己变得更大了)
dp[6] = 6(nums[6]=1加上dp[5]=5让自己变得更大了)
1
2
3
4
5
6
7
8

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        length = len(nums)
        if length == 0: return 0
        dp = [0] * length
        res = nums[0]                                           # 记录历史最大和,不管nums[0]是正是负,res初始值都是它

        dp[0] = nums[0]                                         # 虽然nums[0]有可能是负的,但是舍不掉
        for i in range(1, length):
            dp[i] = max(dp[i - 1], 0) + nums[i]
            res = max(res,dp[i])
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

4.最长回文子串LeetCode5

难度：中等Medium

因为定义两个指针i和j，故动态规划数组dp是二维的。
状态dp[i][j]：代表子串s[i…j]是否是回文字符串(左闭右闭)
状态转移方程: dp[i][j]要看s[i]和s[j]是否相等且dp[i+1][j-1]是否是回文字符串,即i和j各向里走一步.
$\&\& (j - i < 3 || dp[i + 1][j - 1])$

class Solution {
public:
    string longestPalindrome(string s) {
        int length = s.size();                                  // 养成好习惯
        int maxLength = INT_MIN;
        int end = 0, start = 0;
        vector<vector<bool>> dp(length, vector<bool>(length));  // vector<bool>(length)赋值length个第一行
        for (int i = length - 1; i >= 0; i--) {                 // i从后往前,则j从i到头;若i从前往后走,则j从0到i
            for (int j = i; j < length; j++) {
                dp[i][j] = (s[i] == s[j]) && (j - i < 3 || dp[i + 1][j - 1]);  // 状态转移方程看两个元素s[i] == s[j]和dp[i + 1][j - 1]
                if(dp[i][j] && (j - i) > maxLength) {           // 当找到更长的元素时,找两个东西:起始坐标start和长度maxLength
                    start = i;
                    end = j;
                    maxLength = j - i;
                }
            }
        }
        return s.substr(start, maxLength + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5.接雨水LeetCode42

难度：困难Hard

idea: 动态规划(DP method)
用两个指针left和right代表当前水柱的下标,分别指向两端;
另外再定义两个变量:left_max:代表height[0…left]的最高柱子高度,right_max:代表height[right…end]的最高柱子高度,类比第53题最大子序和:dp[i]代表从[0…i]的最大和.
对于每一轮做两次判断:
1.更新当前left_max和right_max的大小;
2.再比较left_max和right_max的大小:
a. 若left_max小,则用left_max减去height[left]的高度,求height[left]这一列盛水的面积;
b. 若right_max小,则用right_max减去height[right]的高度,求height[right]这一列盛水的面积;
也可以:
1.比较height[left]和height[right]的大小;
a.若height[left]小,先更新left_max,再计算height[left]能盛水的体积
b.若height[right]小,先更新right_max,再计算height[right]能盛水的体积
注意到这种方法求盛水面积是一列一列计算的,而用栈的方法是一行一行计算的

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;                // 定义左右两个指针
        int res = 0;                                            // 最大盛水的面积
        int left_max = 0, right_max = 0;
        while(left <= right) {                                  // 当两个指针还没相交时
            if(height[left] <= height[right] ) {
                if(height[left] >= left_max) left_max = height[left];
                res += left_max - height[left];
                left++;
            } else {
                if(height[right] >= right_max) right_max = height[right];
                res += right_max - height[right];
                right--;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

6.戳气球LeetCode312

难度：困难Hard

分别定义状态dp[i][j]和状态转移方程
状态dp[i][j]: 不戳破nums[i]和nums[j],仅戳破i和j之间的气球能得到的最大金币数
状态转移方程: dp[i][j] = dp[i][k] + dp[k][j] + nums[i][j][k],因为dp[i][k]是戳破[i…k]之间的气球, dp[k][j]是戳破[k…j]之间的气球,故[i…j]之间只剩一个气球,就是nums[k],戳破它得到的金币数为: nums[i] * nums[k] * nums[j] 即nums[i][j][k],故
dp[i][j] = dp[i][k] + dp[k][j] + nums[i][j][k] = dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]
(注意此时nums[i]和nums[j]还没有被戳破)
定义3个指针i、j和k,i是最外层,从后往前; j是中间层, 从i+2到最后, 对于nums[i]和nums[j]之间的每一个气球nums[k]都戳一戳试试,即
for(int k = i + 1; k < j; k++) {
int temp = dp[i][k] + dp[k][j] + nums2[i] * nums2[k] * nums2[j];
}
因为从nums[i]到nums[j]中间会尝试好多好多次,故不能直接把结果赋给dp[i][j],故再定义一个变量max,当尝试了所有可能的k后,找到最大的temp再赋给dp[i][j]

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]                                # 因为要戳破两头的气球,故把原数组加长 
        length = len(nums)
        dp = [[0] * length for _ in range(length)]             # 建立二维数组,混合了乘法和for循环

        for i in range(length - 1, -1, -1):                    # 从[n-1]取到[0],每次往左走1步
            for j in range(i + 2, length):                     # i是从[i+2]取到[n-1]
                
                for k in range(i + 1, j):                      # k是从[i+1]取到[j-1]
                    dp[i][j] = max(dp[i][j], nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]) # 还是Python方便,当k遍历过程中,dp[i][j]始终保持最大
        
        return dp[0][length - 1]                               # 不戳破nums[0]和nums[length-1],因为本来就是额外添加上去的
1
2
3
4
5
6
7
8
9
10
11
12
13

7.最大矩形LeetCode85

难度：困难Hard

idea: 暴力法(brute force)
每一行记录以当前数字结尾的连续1的个数,把每个数字都记录好之后宽也就出来了,不过这只是"高度为1"时的宽,要想求更大的面积还要往上倒,找到"高度为2时的宽",“高度为3时的宽”,来求最大面积

e.g
matrix = 
[
  [1,0,1,0,0]
  [1,0,1,1,1]
  [1,1,1,1,1]
  [1,0,0,1,0]
]
width = 
[
  [1,0,1,0,0]
  [1,0,1,2,3]
  [1,2,3,4,5]
  [1,0,0,1,0]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

例如width[2][2]=3这个点,以它为矩阵右下角的点时,高为1,宽为3;往上倒,当高为2的时候发现以matrix[1][2]为宽就只剩1了,取两个宽的较小值:Math.min(width[2][2],matrix[1][2])=1,求最大面积;
再例如width[2][4]=5这个点,以它为矩阵右下角的点时,高为1,宽为5;往上倒,当高为2的时候发现以matrix[1][4]为宽就只剩3了,取两个宽的较小值:Math.min(width[2][4],matrix[1][4])=3,求最大面积;

/* 暴力法 */
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        // 保存以当前数字结尾的连续1的个数
        int[][] width = new int[matrix.length][matrix[0].length];
        int maxArea = 0;
        // 遍历每一行
        for (int row = 0; row < matrix.length; row++) {                     // 行数从上往下
            for (int col = 0; col < matrix[0].length; col++) {              // 列数从左往右
                // 当某一行找到了一个1,看它左边还有多少个连续的1
                if (matrix[row][col] == '1') {
                    if (col == 0) {                                         // 如果是第一列的1
                        width[row][col] = 1;
                    } else {                                                // 如果不是第一列的1
                        width[row][col] = width[row][col - 1] + 1;
                    }
                } else {
                    width[row][col] = 0;
                }
                // 先Mark一下以当前数字结尾作为宽
                int minWidth = width[row][col];
                // 按当前数字同一列往上找更小的值,作为矩阵的宽
                for (int up_row = row; up_row >= 0; up_row--) {
                    int height = row - up_row + 1;                          // 求一下高度(注意1的高度差)
                    // 同一列需要找到最小的数作为矩阵的宽
                    minWidth = Math.min(minWidth, width[up_row][col]);
                    // 每次更新面积
                    maxArea = Math.max(maxArea, height * minWidth);
                }
            }
        }
        return maxArea;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

idea: 动态规划(DP method)
跟接雨水那题类似,用两个变量leftLessMax[i]和rightLessMin[i]分别记录当下标为i时,紧挨着它的左边和右边的仅次于它的高度,另外再定义一个变量height[i],记录当前下标i对应的1的高度.

e.g
matrix = 
[
  [1,0,1,0,0]
  [1,0,1,1,1]
  [1,1,1,1,1]
  [1,0,0,1,0]
]
1
2
3
4
5
6
7
8

第一行遍历结束: height = [1,0,1,0,0]; 第二行遍历结束: height = [2,0,2,1,1]; 第三行遍历结束: height = [3,1,3,2,2]; 第四行遍历结束: height = [4,0,0,3,0];
leftLessMax赋值结束后:

[
    b=-1 L[col]=-1, b=1  L[col]=-1, b=1  L[col]=1, b=3  L[col]=-1, b=4  L[col]=-1
    b=-1 L[col]=-1, b=1  L[col]=-1, b=1  L[col]=1, b=1  L[col]=1,  b=1  L[col]=1
    b=-1 L[col]=-1, b=-1 L[col]=-1, b=-1 L[col]=1, b=-1 L[col]=1,  b=-1 L[col]=1
    b=-1 L[col]=-1, b=1  L[col]=-1, b=2  L[col]=-1,b=2  L[col]=2,  b=4  L[col]=-1
]
1
2
3
4
5
6

每次遇到matrix[row][col]=1时,leftLessMax[col]看左边boundary界限的下标和当前列上一个leftLessMax[col]谁更大点,取较大的;
每次遇到matrix[row][col]=0时,把它作为boundary左边的边界,leftLessMax[col]置-1,不会对当前列下面的所有1有作用了

/* 动态规划 */
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int maxArea = 0;
        int cols = matrix[0].length;                                      // cols记录一共有多少列
        int[] leftLessMax = new int[cols];
        int[] rightLessMin = new int[cols];
        // 把每个leftLessMax都初始化为-1,即左边比当前高度height[i]稍矮的是最左边的位置
        Arrays.fill(leftLessMax, -1);
        // 把每个rightLessMin都初始化为cols,即右边比当前高度height[i]矮的是最右边的位置
        Arrays.fill(rightLessMin, cols);
        // 按行从上往下遍历,到当前行的某个数字时的当前列的高度
        int[] heights = new int[cols];
        for(int row = 0; row < matrix.length; row++) {
            // 更新所有高度,过程见最上面注释
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') {
                    heights[col] += 1;
                } else {
                    heights[col] = 0;
                }
            }
            // 更新所有leftLessMax
            // 注意: boundary是计算别的leftLessMax用的,而leftLessMax[i]是计算面积用的
            int boundary = -1;                                  // 记录上次出现0的位置,即左边的门神
            for(int col = 0; col < cols; col++) {
                if(matrix[row][col] == '1') {
                    // 当找到"1"时,拿该列上一个位置的leftLessMax和本行的boundary比较较大值
                    leftLessMax[col] = Math.max(leftLessMax[col], boundary);
                } else {
                    // 当前是0代表当前坐标没有高度,更谈不少"紧挨着它的左边的较小高度"了,所以初始化为-1,以后不考虑它了
                    leftLessMax[col] = -1; 
                    //更新0的位置
                    boundary = col;
                }
            }
            // 更新所有rightLessMin
            boundary = cols;
            for (int col = cols - 1; col >= 0; col--) {
                if (matrix[row][col] == '1') {
                    rightLessMin[col] = Math.min(rightLessMin[col], boundary);
                } else {
                    rightLessMin[col] = cols;
                    boundary = col;
                }
            }
            
            // 更新所有面积
            for (int col = cols - 1; col >= 0; col--) {
                // 矩形的高为heights[col](纵向),宽为rightLessMin[col]-leftLessMax[col]-1(横向)
                int area = (rightLessMin[col] - leftLessMax[col] - 1) * heights[col];
                maxArea = Math.max(area, maxArea);
            }

        }
        return maxArea;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

8.编辑距离LeetCode72

难度：困难Hard

idea: 动态规划(DP method)
状态dp[i][j]: 代表word1从[0]到[i]和word2从[0]到[j]的编辑距离是多少
状态转移方程,分两种情况: (word1和word2都从后往前看)
1.当word1[i] == word2[j]时, 例如word1=“abcd”,word2=“xyd”,则word1[3]==word2[2],则当前没有新增编辑距离,看各自前一位的状态,即 dp[3][2]=dp[2][i]
2.当word1[i] ！= wrod2[j]时, 例如word1=“horse”, word2=“ros”,则需要增加编辑距离了：
a.状态1: dp[i-1][j],相当于打掉word1的最后一个字母(编辑距离+1),即word1=“hors”,比较word1[0…i-1]和word2[0…j]的编辑距离: dp[i-1][j],或者是给word2增加一个word1的最后一个字母(编辑距离+1),即word2=“rose”,也是一样的.
b.状态2: dp[i][j-1],相当于打掉word2的最后一个字母(编辑距离+1),即word2=“ro”,比较word1[0…i]和word2[0…j-1]的编辑距离: dp[i][j-1],或者是给word1增加一个word2的最后一个字母(编辑距离+1),即word1=“horses”,也是一样的.
c.状态3: dp[i-1][j-1],相当于更改word1的最后一个字母或更改word2的最后一个字母(编辑距离+1),即word1="horss"了,或者word2="roe"了,比较word1[0…i-1]和word2[0…j-1]的编辑距离: dp[i-1][j-1]

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));   // 建立二维数组(考虑到word1或word2有可能为0,故多申请一个空间),行为m+1,列为n+1,全部填充0
        for(int i = 1; i <= m; i++) {                      // 当word2为空时,word1的长度即编辑距离的大小
            dp[i][0] = i;
        }
        for(int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        // 自底至顶填充
        for(int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {         // 因为dp[i][j]多申请了一行空间,故dp[i][j]的状态是看word1[i-1]和word2[j-1]是否相等
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        return dp[m][n];                                    // 返回最后一个状态
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

9.最小路径和 / 矩阵的最小路径和LeetCode64

难度：中等Medium

idea: 动态规划(DP method)
状态dp[i][j]: 代表走到grid[i][j]格子的最小花费;
状态转移方程: 由于走到grid[i][j]格子只能从上面grid[i-1][j]或者左边grid[i][j-1]走过来,故取代表二者状态dp[i-1][j]和dp[i][j-1]的较小值,再加上当前格子的花费grid[i][j]即可:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size(); 
        vector<vector<int>> dp(m, vector<int>(n, grid[0][0]));    // 定义m行n列的数组,赋初值grid[0][0]
        // 首列赋初值,每个格子都只能从上面走过来
        for (int i = 1; i < m; i++)
        {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        // 首行赋初值,每个格子都只能从左边走过来
        for (int j = 1; j < n; j++)
        {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        // 一般情况,去左边和上面状态的较小者加当前格子的花费,即为当前格子的状态
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
        	{
                dp[i][j]  = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        	}
        }

        return dp[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

10.不同路径 / 矩阵的总路径数LeetCode62

难度：中等Medium

idea: 动态规划(DP method)
由题意只到某一个格子[i][j]只能从上面[i-1][j]和左边[i][j-1]走过来,故走到当前格子的方法数为二者之和
状态dp[i][j]: 代表走到第[i][j]格子的方法数
状态转移方程: dp[i][j] = dp[i-1][j] + dp[i][j-1]

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));           // 建立一个m*n的二维矩阵dp,全都赋初值1
        // 由于在第一行走和在第一列走都只有1中方法,故不用再特殊赋初值了
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

11.区域和检索 - 数组不可变 / 数组区间和LeetCode303

idea: 动态规划(DP method)
状态dp[i]: nums从[0]到[i-1]的和是多少, dp数组的大小比nums多1
状态转移方程: dp[i+1] = dp[i] + nums[i]
求从nums[i]到nums[j]的和是多少,包含nums[i]和nums[j], dp[i]是从nums[0]到nums[i-1]的和,dp[j+1]是从nums[0]到nums[j]的和,中间的差正好是从nums[i]到nums[j]

class NumArray {
private:
    vector<int> dp;                                            // 因为vector是动态大小的,故不用定义大小
public:
    NumArray(vector<int>& nums) {
        dp.push_back(0);
        for(int num : nums)
            dp.push_back(dp.back() + num);
    }

    int sumRange(int left, int right) {
        return dp[right + 1] - dp[left];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

12.等差数列划分 / 数组中等差递增子区间的个数LeetCode413

难度：中等Medium

idea: 动态规划(DP method)
状态dp[i]: 以A[i]结尾的等差序列个数,
状态转移方程
1.若找到新的A[i]-A[i-1]==A[i-1]-A[i-2],则dp[i]=dp[i-1]+1,最后把所有的dp都加起来即可
e.g
A = [0,1,2,3,4]
dp[2] = 1, 此时只有[0,1,2]
dp[3] = dp[2] + 1,此时在[0,1,2]的基础上多了一个1,2,3
dp[4] = dp[3] + 1,此时在0,1,2和1,2,3的基础上多了一个[2,3,4],
最后把dp[2]代表的[0,1,2],dp[3]代表的[0,1,2,3]和[1,2,3],dp[4]代表的[0,1,2,3,4],[1,2,3,4]和[2,3,4]都加到一起即可
2.若没找到,则此时的dp[i]置为0

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        vector<int> dp(A.size());                                    // 建立dp数组,大小为数组A的大小
        int res = 0;
        if(A.size() < 3) return res;                                 // 根本构不成3个序列
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < A.size(); i++) 
        {
            if(A[i - 1] - A[i - 2] == A[i] - A[i - 1])
            {
                dp[i] = dp[i - 1] + 1;
                res += dp[i];
            } else {
                dp[i] = 0;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

12.解码方法 / 分割整数构成字母字符串LeetCode91

难度：中等Medium

idea: 动态规划(DP method)
状态dp[i]: 从s的第1个数到s的第i个数的总的解码方法数,(由于是字符串题目,故多申请一个空间,代表空字符串)
本题采用加腿的思路,主要是看后两位能否单独构成字符串,即看 $s [i - 1] 和 s [i]$ ,若能构成单独字符串,则 $d p [i] = d p [i - 1] + d p [i - 2]$ (相当于既可以把 $s [i]$ 加到 $s [0 . . . i - 1])$ 上,也可以把 $s [i - 1]$ s $[i]$ 作为整体加到 $s [0 . . . i - 2]$ 上),若不能单独构成字符串,则 $d p [i] = d p [i - 2]$ (此时相当于把 $s [i - 1] s [i]$ 作为整体加到 $s [0 . . . i - 2]$ 上),举两个例子:

e.g1: s = "22624"
226:3种方法 2 -> 2 -> 6; 2 -> 26; 22 -> 6;
2262:3种方法 2 -> 2 -> 6 -> 2; 2 -> 26 -> 2; 22 -> 6 -> 2; (即看后两位62,它不能作为一个整体加到前两个数"22"上,故只能把最后一位2加到前三个数"226"上)
22624: 6种方法 2 -> 2 -> 6 -> 2 -> 4    (把2加到2262上)
                          -> 24        (把24加到226上)
              2 -> 26     -> 2 -> 4    (把2加到2262上)
                          -> 24        (把24加到226上)
              22 -> 6     -> 2 -> 4    (把2加到2262上)
                          -> 24        (把24加到226上)
e.g2: s = "210"
2: 1种方法: 2
21: 2种方法: 2 -> 1; 21 (看后两位"21",既可以把1加到2上,也可以把21当作整体加到空字符串" "上)
210: 1种方法: 2 -> 10 (看后两位"10",只能把它当作整体加到第一位"2"上)
1
2
3
4
5
6
7
8
9
10
11
12
13

12.最长递增子序列LeetCode300

难度：中等Medium

状态dp[i]: 代表以nums[i]结尾的最长的递增子序列的长度, 初始均为1,代表它们本身
状态转移方程: 当遍历到nums[i]时,依次比较从nums[0]到nums[i-1]与nums[i]的大小,若nums[i] > nums[j],则在nums[j]对应的状态dp[j]基础上+1,即可以把nums[i]加在nums[j]后面,可以构成更长的上升子序列,并比较+1后的dp[j]和dp[i]的大小,取较大者.
e.g nums = [1,3,4,5,2,9],
当遍历到nums[5]=9时, 此时dp[0] = 1, dp[1] = 2, dp[2] = 3, dp[3] = 4, dp[4] = 2
nums[5] > nums[0], 更新dp[5]: dp[5] = 2, 即上升序列可以为[1,9]
nums[5] > nums[1], 更新dp[5]: dp[5] = 3, 即上升序列可以为[1,3,9]
nums[5] > nums[2], 更新dp[5]: dp[5] = 4, 即上升序列可以为[1,3,4,9]
nums[5] > nums[3], 更新dp[5]: dp[5] = 5, 即上升序列可以为[1,3,4,5,9]
nums[5] > nums[4], 更新dp[5]: max(dp[4]+1, dp[5]) = max(3, 5) = 5,

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        const int size = nums.size();                               // 前面加个const,代表不能改变了
        if (size == 0) { return 0; } 
        vector<int> dp(size, 1);                                    // 申请大小为size的数组,初始值均为1
        int res = 1;
        for (int i = 1; i < size; ++i) {
            for (int j = 0; j < i; ++j) {                         // 拿nums[i]分别和nums[0]到nums[j]比
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);                  // 每次都尝试更新一下dp[i]
                }
            }
            // 最长上升序列不一定是在以nums[n]结尾的数上, dp长度是参差不齐的.
            res = max(res, dp[i]);                        // 要是python就方便了,直接取所有dp[i]的最大值
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

状态方程dp[i]: 以nums[i]为结尾的最长上升子序列的长度,初始dp[i]都等于1,意思是所有的数自己也是一个上升子序列
状态转移方程:
对于每一个数nums[i],for循环j从[0]遍历到[i-1],比较nums[i]与每一个nums[j]的大小, 若nums[i]>nums[j], 证明nums[i]可以放在nums[j]的后面,即找到了以nums[i]结尾的更长的上升序列,此时看nums[j]对应的dp[j]加1后是否比当前的dp[i]长,若更长,则更新dp[i], 由于数组大小是参差不齐的,所以最终返回dp数组里最大的(而不是最后一个dp[-1])
e.g nums = [10,9,2,5,3,7,101,18],
当nums[6] = 101时,初始dp[6]=1
此时dp[0]=1, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=2, dp[5]=3, dp[6]=1
定住nums[6], 依次比较(nums[0]到nums[5])和nums[6]的大小,
nums[6] > nums[0], 可以更新dp[6]了: dp[6] = max(dp[0]+1, dp[6]) = max(1+1, 1) = 2; 此时最长上升子序列为[10,101]
nums[6] > nums[1], 又可以更新dp[6]了: dp[6] = max(dp[1]+1, dp[6]) = max(1+1, 2) = 2; 此时最长上升子序列为[9,101]
nums[6] > nums[2], 又双可以更新dp[6]了: dp[6] = max(dp[2]+1, dp[6]) = max(1+1, 2) = 2; 此时最长上升子序列为[2,101]
nums[6] > nums[3], 又双叒可以更新dp[6]了: dp[6] = max(dp[3]+1, dp[6]) = max(2+1, 2) = 3; 此时最长上升子序列为[2,5,101]
nums[6] > nums[4], 又双叒叕可以更新dp[6]了: dp[6] = max(dp[4]+1, dp[6]) = max(2+1, 3) = 3; 此时最长上升子序列为[2,5,7,101]
依次类推

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        if not nums: 
            return 0
        length = len(nums)                                             # 养成好习惯
        
        # dp数组初始化,每个初始都为1,表示每个数本身就是一个上升子序列
        dp = [1] * length                                            # c++: vector<int> dp(length, 1)
        
        # 正片开始
        # 外层i从[0]到[length-1],对于每一个i,内层j从[0]到[i-1]
        for i in range(length):
            for j in range(i):
                if nums[i] > nums[j]:                                  # 当发现一个nums[i]大于nums[j]时,证明有门,可以更新dp[i]了(即可以把nums[i]放在nums[j]后面,dp[j]变长了1)
                    dp[i] = max(dp[i], dp[j] + 1)
                    # 此处也可以用一个数res记录最大长度,每次更新完dp[i]后,再拿它和历史最大res比
        
        return max(dp)                                                 # 返回dp里最大的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

13.最长递增子序列个数Leetcode673

状态方程:

(与最长递增子序列Leetcode300类似),dp[i]:以nums[i]结尾的最长递增子序列的长度;
cnt[i]: 以nums[i]结尾的最长递增子序列的个数,

例如dp[i]=5, cnt[i]=2,即以nums[i]结尾的最长递增子序列长度是5,一共有两个.
状态转移方程: 外层还是从0开始遍历,当遍历到第i个数nums[i]时,内层j从0到i-1. 每发现nums[i] > nums[j]时就可以更新dp[i]和cnt[i]了:
dp[i] = max(dp[i], dp[j] + 1)看看是否有更长的递增子序列了;
cnt[i]的更新分两种情况:
a.当dp[j] + 1 > 原dp[i]时,证明找到了一个更长的递增子序列, 此时更新dp[i],对于cnt[i],直接继承cnt[j]即可: cnt[i]=cnt[j],代表从nums[j]后面接了一个nums[i],还是原来那些递增序列,只不过变长了.
b. 当dp[j] + 1 == 原dp[i]时, 证明之前有dp[j]+1这种长度的子序列了,且以nums[i]结尾的,现在又来了cnt[j]个,就在cnt[i]的基础上加上cnt[j]即可.
举个简单的例子:

e.g nums=[1,3,5,4,7],当遍历到nums[4]=7时
nums[4] > nums[2], 更新dp[4] = dp[2]+1=4; cnt[4]=cnt[2]=1(继承cnt[2]的个数)
nums[4] > nums[3], 再次更新dp[4]: dp[3]+1=dp[4](均为4),证明之前存在dp[3]+1长度的子序列了,此时
更新cnt[4]就需要用新的加上老的: cnt[4] = cnt[4] + cnt[3]
                                        旧的     新的(继承cnt[3]的)
1
2
3
4
5

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, res = 0, max_len = 0;
        int[] len =  new int[n], cnt = new int[n];
        for(int i = 0; i<n; i++){
            len[i] = cnt[i] = 1;
            for(int j = 0; j <i ; j++){
                if(nums[i] > nums[j]){
                    if(len[i] == len[j] + 1) cnt[i] += cnt[j];  // 证明以前出现过len[j]+1长度的序列了,总个数为之前cnt[j]+1的个数cnt[i]和新的cnt[j]+1的个数求和
                    if(len[i] < len[j] + 1){                    // 找到新的最长长度的递增子序列了
                        len[i] = len[j] + 1;                    // 更新最长长度
                        cnt[i] = cnt[j];                        // cnt直接继承旧的(相当于在nums[j]的后面加了个nums[i],个数还是原来的个数)
                    }
                }
            }

            if(max_len == len[i]) res += cnt[i];        // 每比较完一组nums[i]就要看看得到的cnt[i]与历史最多那个大,若是相同,就把结果相加.例如以nums[i]结尾的最长递增子序列长度为5,有2个,此时max_len=5,res=2; 后来又找到以nums[j]结尾的最长子序列长度同样为5(都是最长长度),有3个,则res要加上cnt[j]: res = res + cnt[j]
            if(max_len < len[i]) {
                max_len = len[i];
                res = cnt[i];
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

14.无重叠区间LeetCode435

状态方程dp[i]: 代表以i为结尾的最长上升子序列的长度
首先按每个子元素的第二个数字排序,即按右端点排序,(若右端点一样,左端点大的在后面)
初始长度依旧是1,代表它本身,对每一个子列表intervals[i],用它的左端点intervals[i][0]往前找最接近的右端点intervals[j][1].当找到第一个的时候intervals[j],代表它的右端点intervals[j][1]一定是与当前列表的左端点intervals[i][0]最靠近的,且找到的第一个的左端点intervals[j][0]一定是离它自己的右端点intervals[j][1]较近的.找到左边第一个右端点比它左端点小的就可以了,因为是按右端点排序过的,左边第一个肯定是最接近它的左端点的.
e.g 排序完之后
[[1,2],[6,7],[2.5,1000],[998,1000],[1002,1005]]
初始:dp[0]=1, dp[1]=1, dp[2]=1, dp[3]=1, dp[4]=1
第一轮: dp[0]=1, dp[1]=2,
第二轮: dp[0]=1, dp[1]=2, dp[2]=2,
第三轮: dp[0]=1, dp[1]=2, dp[2]=2, dp[3]=3,

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)                                             # 养成好习惯
        if n == 0: return 0
        dp = [1] * n                                                   # 初始赋为1,代表子列表本身
        res = 1
        intervals.sort(key = lambda a: (a[1],a[0]))                    # 先按每个子元素的第二个数字排序,若相同,再按第一个数字排序

        for i in range(len(intervals)):
            for j in range(i - 1, -1, -1):
                if intervals[i][0] >= intervals[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    # 由于最开始排序了,故倒着找的时候,找到的第一个一定是最大的数,因此不用往前继续找了
                    break
            
            dp[i] = max(dp[i], dp[i - 1])                             # 想不通这一步在干嘛
            res = max(res, dp[i])

        return n - res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

idea: 贪心算法(greedy method)
假设从前往后遍历,无非就是拿当前的start跟之前的end比,若start比end大,则证明个数+1;
假设从后往前遍历,无非就是拿当前的end跟之前的start比,若end比start小,则证明个数+1;
下面就是看是按start排序还是按end排序了,目的是要防止捣乱的,例如[3,10000]这种,如果按start排,并且从前往后遍历,这种就会排在前面,这是不愿意看到的,故按end排序.
形象地形容一下,当从前往后遍历时,张开双臂,从起点朝向终点,要把尽可能多的子序列收进来,肯定是要让end越小越好.
同理从后往前遍历时,要让[3,10000]这种尽可能放到前面,故按start排即可

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)                                  # 养成好习惯
        intervals.sort(key = lambda x: x[1])                # 从前往后遍历时,要按end排序
        end = -float('inf')
        res = 0
        for i in intervals:                                 # 从前往后遍历
            start = i[0]
            if start >= end:
                res += 1
                end = i[1]
        
        return n - res
1
2
3
4
5
6
7
8
9
10
11
12
13

15.最长数对链 / 一组整数对能够构成的最长链LeetCode646

idea: 动态规划(DP method)
把所有的数对按升序排序,先按第[0]维排序,若第[0]维相等再看第[1]维.
状态dp[i]: 以第[i]个数对结尾的最长数对链的个数
状态转移方程: 对于第[i]个数对pairs[i],分别拿第[0]个到第[i-1]个数对的尾[1]与它的头[0]进行对比,若头大于尾,则更新dp[i]

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        if (pairs.empty()) return 0;
        // 定义排序数组sort,按从小到大排序;先看第[0]维,即先看头,若头相等,则再看尾
        sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b){
            return (a[0] == b[0] && a[1] < b[1]) || (a[0] < b[0]);
        });

        int n = pairs.size(), res = 0;
        vector<int> dp(n, 1);
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                if(pairs[j][1] < pairs[i][0]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);                                  // 每看完一轮dp[i]都更新下结果,因为最后dp长度是参差不齐的.
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

16.摆动序列 / 最长摆动子序列LeetCode646

难度：中等Medium

idea: 动态规划(DP method)
定义两个状态: up[i]: 表示最后两个数字递增的最长摆动序列的长度;
down[i]: 表示最后两个数字递减的摆动序列的长度;
状态转移方程:
当nums[i] > nums[j]时,证明该上升了,更新up[i+1], 找到前一个down[i],再此基础上+1,即up[i+1] = down[i] + 1;
当nums[i] < nums[j]时,证明该下降了,更新down[i+1], 找到前一个up[i],再此基础上+1,即down[i+1] = up[i] + 1;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int size = nums.size();
        
        if (size == 0) {
            return 0;
        }

        vector<int> up(size, 0);                                    // 定义上升dp数组,初始值均为0
        vector<int> down(size, 0);                                  // 定义下降dp数组,初始值均为0
        up[0] = 1;
        down[0] = 1;
        for(int i = 1; i < size; ++i)
        {    
            if (nums[i] > nums[i - 1]) {                            // 找到了一个上升对,更新up(在前一个down的基础上)
                up[i] = down[i - 1] + 1;
                down[i] = down[i - 1];                              // 下降的不用更新,长度跟以前一样
            }
            else if (nums[i] < nums[i - 1]) {
                down[i] = up[i - 1] + 1;
                up[i] = up[i - 1];
            }
            else {                                                  // nums[i]和nums[i-1]相等,都不更新
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }
        return max(up[size - 1], down[size - 1]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

17.最长公共子序列LeetCode1143

idea: 动态规划(DP method)
因为是两个字符串,类比编辑距离那道题,故要定义二维dp数组,因为是字符串题目,故要多申请一个空间,代表空字符串情况
状态dp[i][j]: 代表text1的第[0…i]和text2的第[0…j]为止公共序列的长度;
状态转移方程:
a.当text1[i]==text2[j]时,证明找到了新的更长的公共子序列,在原来的基础上+1: dp[i][j] = dp[i-1][j-1] + 1
b.当text1[i]!=text2[j]时,text1往里收一位(看text1[0…i-1]和text2[0…j])或者text2往里收一位,即dp[i][j]由dp[i-1][j]或者dp[i][j-1]中的较大者决定

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // 申请二维dp数组,行为text1.size()+1,列为text2.size()+1,初始值均为0,就不用赋边界值了
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {           // 注意字符串题目给定字符串始终比dp下标小1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[text1.size()][text2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

18.0-1背包问题

问题描述：
有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

状态dp[i][j]: 表示前i件商品体积最大为j时能获得的最大价值
状态转移方程：根据第[i]件物品是否放入背包中分为两种情况：

第[i]件商品放入背包中：则至少需要留w的体积，则上一个状态最大的体积变为：j-w，上一个状态为dp[i-1][j-w].
第[i]件商品未放入背包中：当前不占用新的体积，上一个状态最大体积仍旧是j，上一个状态为dp[i-1][j].
取二者的较大值：
$d p [i] [j] = m a x (d p [i - 1] [j - w], d p [i - 1] [j])$

// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; j++) {
            if (j >= w) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N][W];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

19.分割等和子集 / 划分数组为和相等的两部分LeetCode416

难度：中等Medium

idea: 动态规划(DP method)
状态dp[i][j]: 从前nums[0…i]个数中选出一些数,使其和为j
状态转移方程:
类比0-1背包问题,对于每个数nums[i]可以选或者不选

选nums[i]时,则前[0…i-1]个数和变为j-nums[i]: dp[i-1][j-nums[i]];
不选nums[i]时,则前[0…i-1]个数的和依旧为j: dp[i-1][j];
当前面的状态为true时,即找到了和为j的若干个数,则当前状态dp[i][j]也为true, 找不到同为false;
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[j]],二者只要有一个为true则dp[i][j]就为true;

e.g nums = [1,5,10,6], 定义一个4行,12列(和的一半为11)的二维数组:
    __,__,__,__,__,__,__,__,__,__,__,__,
    __,__,__,__,__,__,__,__,__,__,__,__,
    __,__,__,__,__,__,__,__,__,__,__,__,
    __,__,__,__,__,__,__,__,__,__,__,__,
1
2
3
4
5

开始赋值,第一行代表只能用1,此时除了dp[0][1]是T,其他的都为F(因为用nums[0]自己去填自己肯定是T)
填第二行,只能用[1,5],先把第一行的结果抄下来,即dp[1][1] = T,(因为用[1,5]两个数,去填1,肯定可以);
第二行填两个值: dp[1][5] = dp[0]5 || dp[0]0,两个均为false,故dp[1][5] = F;
dp[1][6] = dp[0]6 || dp[0]1,两个均为true,故dp[1][5] = T;

class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        // 把给定的数组加起来,并且得到其值的一半,作为背包的最大容积
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 若sum为奇数,则不能二等分
        if ((sum & 1) == 1) {               // 奇数时"101101" & "1" = 1
            return false;
        }

        int target = sum / 2;
        // 类比0-1背包问题,创建二维状态数组,行:物品索引(本题为数字下标),列:容量(本题为总和target)
        boolean[][] dp = new boolean[len][target + 1];

        // 先填表格第0行,第1个数只能让容积为它自己的背包恰好装满
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }
        // 再填表格后面几行
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                // 直接从上一行先把结果抄下来，然后再修正
                dp[i][j] = dp[i - 1][j];

                if (nums[i] == j) {                // 终于找到了,之前的i-1个数都不用了,就用nums[i]这一个
                    dp[i][j] = true;
                    continue;
                }
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

20.目标和 / 改变一组数的正负号使得它们的和为一给定数LeetCode494

难度：中等Medium

状态dp[i][j]：从[0…i-1]个数能凑出[j]的方法数
状态转移方程：当当前的数字1选择+号时，剩下的数字需要凑够的和为：j+nums[i]，当当前的数字选择-号时，剩下的数字需要凑够的和为：j-nums[i]

class Solution {
    public static int findTargetSumWays(int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        // 绝对值范围超过了sum的绝对值范围则无法得到
        if (Math.abs(s) > Math.abs(sum)) return 0;

        int len = nums.length;
        // - 0 +
        int t = sum * 2 + 1;
        int[][] dp = new int[len][t];
        // 初始化
        if (nums[0] == 0) {
            dp[0][sum] = 2;
        } else {
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < t; j++) {
                // 边界
                int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
                int r = (j + nums[i]) < t ? j + nums[i] : 0;
                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
            }
        }
        return dp[len - 1][sum + s];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

21.一和零 / 01 字符构成最多的字符串LeetCode474

idea: 动态规划(DP method)
定义状态dp[i][j][k], 从第[0]个到底[i]个字符串用的字符串包含[j]个0[k]个1的个数的最大字符串个数
状态转移方程: 对于一个新的字符串dp[i],其包含ones个[1]和zeros个[0],用它(上一个状态为dp[i - 1][j - zeros][k - ones]),最大字符串个数+1,或者不用dp[i - 1][j][k]个数较多的

class Solution {

    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len + 1][m + 1][n + 1];

        for (int i = 1; i <= len; i++) {
            // 注意：有一位偏移
            int[] count = countZeroAndOne(strs[i - 1]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    // 先把上一行抄下来
                    dp[i][j][k] = dp[i - 1][j][k];
                    int zeros = count[0];
                    int ones = count[1];
                    if (j >= zeros && k >= ones) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }
    // 对于一个新的字符串,统计"0"和"1"的个数
    private int[] countZeroAndOne(String str) {
        int[] cnt = new int[2];
        for (char c : str.toCharArray()) {
            cnt[c - '0']++;
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

22.零钱兑换 / 找零钱的最少硬币数LeetCode322

idea: 动态规划(DP method)
状态dp[i]: 当剩余总金额为i时凑够它需要的最小硬币数;
状态转移方程:
因为对于从1到amount每一个金额,都要用所有的硬币去尝试,故代表amount的for循环在外层,代表coins的for循环在内层.
dp[i] = min(dp[i], dp[i-coin]+1), 即对于每一个coin都要尝试更新dp[i]

/*动态规划*/
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);                      // 即对于每一个金额i,都用1块的硬币来买
        dp[0] = 0;                                            // 对于金额0,不需要硬币凑,置为0
        for (int i = 1; i <= amount; i++) {                   // 对于从1到amount的每一个金额i
            for (int j = 0; j < coins.size(); j++) {          // 用每一个硬币去尝试,然后更新dp[i]
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];         // 因为dp的初始值为amount+1,若还是该值证明dp[amount]未更新
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

23.零钱兑换 II / 找零钱的硬币数组合LeetCode518

idea: 动态规划(DP method)
状态dp[i][j]: 代表用前i个硬币凑出面额为j的方法数
状态转移方程: 对于第i个硬币的金额coins[i],若剩余面额大于coins[i],代表可以用它,为dp[i][j - coins[i - 1]],也可以不用:dp[i - 1][j]; 若剩余面额小于coins[i],就肯定没法用,为dp[i-1][j]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int K = coins.size() + 1;
        int I = amount + 1;
        vector<vector<int>> dp(K, vector<int>(I, 0));             // 表示用前k个硬币凑出金额为i的组合数
        
        // 初始化基本状态
        for (int k = 0; k < coins.size() + 1; k++){
            dp[k][0] = 1;
        }
        for(int j = 1; j <= amount; j++){                                   // 对于某一个剩余金额i
            for (int i = 1; i <= coins.size() ; i++) {                      // 遍历所有硬币coins[k-1]
                if (j >= coins[i - 1]) {
                    dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j];      // 剩余金额大于硬币
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[coins.size()][amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

24.单词拆分 / 字符串按单词列表分割LeetCode139

idea: 动态规划(DP method)
这是个完全背包问题,
状态dp[i]: 剩余字符串长度为i时是否能拆分;
状态转移方程: 当剩余字符串长度为i时,遍历字典中的每一个单词word,看两个东西:

字符串的后len(word)个长度是否为单词word;
字符串减去word后是否还是可拆分的;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(wordDict.size()==0) return false;
        
        set<string> dict;
        for(auto w: wordDict)
            dict.insert(w);

        vector<bool> dp(s.size() + 1,false);
        dp[0] = true;
        
        for(int i = 1; i <= s.size(); i++)
        {
            for(int j = i - 1; j >= 0; j--)
            {
                if(dp[j])
                {
                    string word = s.substr(j, i - j);
                    if(dict.find(word) != dict.end())
                    {
                        dp[i] = true;
                        break;                                      // 跳出当前i,遍历下一个
                    }
                }
            }
        }
        
        return dp[s.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

25.单词拆分 / 字符串按单词列表分割LeetCode139

难度：中等Medium

idea: 动态规划(DP method)
状态dp[i][j]: 用nums的前i个数去凑剩余目标为j的组合个数
状态转移方程: 对于某个剩余目标j,尝试所有的nums数字: nums0, nums1…把它们所有都加起来,即dp[i][j]的总组合数.
可以理解成爬楼梯,到达第[j]阶的总方法数可以由[j-nums[0]],[j-nums[1]]等等爬上来,把它们加起来即可

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i-num]                      # 相当于爬楼梯问题,到第i阶可以由i-nums[0],i-nums[1],i-nums[2]...爬上来

        return dp[target]
1
2
3
4
5
6
7
8
9
10
11
12

26.两个字符串的删除操作 / 删除两个字符串的字符使它们相等LeetCode583

难度：中等Medium

idea: 动态规划(DP method)
定义状态dp[i][j]: word1从[0]到[i-1]和word2从[0]到[j-1]相同时所需的最小步数
状态转移方程:

当word1[i-1]==word2[j-1]时: dp[i][j]=dp[i-1][j-1]
当word1[i-1]!=word2[j-1]时: 要么word1删除一个字母: dp[i-1][j]+1,要么word2删除一个字母: dp[i][j-1]+1,取二者的较小值. min(dp[i-1][j]+1, dp[i][j-1]+1).

class Solution {
    public int minDistance(String word1, String word2) {
        char[] ch1 = word1.toCharArray(), ch2 = word2.toCharArray();    // Java麻烦的一点就在于要把字符串变成字符串数组
        int len1 = word1.length(), len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];             // 字符串题目要多申请一个空间,代表空字符串
        
        // 初始化dp数组,当word1或者word2为空字符串时
        for (int i = 1; i <= len1; i++) dp[i][0] = i;      // 注意word1从[0]到[i-1]是i个字母,不是i-1个
        for (int j = 1; j <= len2; j++) dp[0][j] = j;
        
        // 一般情况,分两种
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (ch1[i - 1] == ch2[j - 1]) {            // 注意dp数组下标始终比word1下标多1,因为dp[0]代表空字符串,而word1[0]代表第一个字母
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }
        return dp[len1][len2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

27.编辑距离LeetCode72

难度：困难Hard

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));   // 建立二维数组(考虑到word1或word2有可能为0,故多申请一个空间),行为m+1,列为n+1,全部填充0
        for(int i = 1; i <= m; i++) {                      // 当word2为空时,word1的长度即编辑距离的大小
            dp[i][0] = i;
        }
        for(int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        // 自底至顶填充
        for(int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {         // 因为dp[i][j]多申请了一行空间,故dp[i][j]的状态是看word1[i-1]和word2[j-1]是否相等
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        return dp[m][n];                                    // 返回最后一个状态
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

28.只有两个键的键盘 / 复制粘贴字符LeetCode650

idea: 动态规划(DP method)
状态dp[i][j]: 当前有i个A,剪切板里此时有j个A了
状态转移方程: dp[i][j]=min(dp[i-j][j]+1, dp[i][j])要得到dp[i][j],当此时有i-j个A时,剪切板里有j个A,很显然就粘贴一下就ok了,即dp[i][j] = dp[i-j][j]+1,后面解答就看不懂了…

class Solution {
public:
	/*650. 只有两个键的键盘 ctrl+c ctrl+v*/
	//思路，满足最优子结构，无后效性，重复子结构，可考虑动态规划
	//阶段： n阶问题，每阶有j个子问题，既可以在已复制j个的基础上粘贴
	//状态： 粘贴之前必须复制（限定条件），复制有j个'A' 当前有‘i’个'A' 
	//状态转移方程：dp[i][j]=min(dp[i-j][j]+1,dp[i][j]);
	//边界条件，每复制一次j个"A"要用一次操作，当i==j的时候可以全部复制
	int minSteps(int n) {
		if (n == 0)
			return 0;
		vector<vector<int>> dp(n + 1);
		for (int i = 0; i <= n; i++)
		{
			dp[i].resize(n + 1,n);//因为是求最小值，这里随便初始化一个值，但是要足够大，分析可知就算是每次只粘贴一个，那么最多操作数是n
		}
		dp[1][1] = 0;				//初始状态
		for (int i = 1; i <= n; i++)
		{
			int minNum = dp[i][1];	//纪录第二层循环的最小值 下面会用到
			for (int j = 1; j <=i; j++)
			{
				if (i - j >= 1)		//注意不要越界
				{
					dp[i][j] = min(dp[i - j][j] + 1, dp[i][j]);	//i个A 要在i-j个A的基础上粘贴j个A
					minNum = min(minNum, dp[i][j]);
				}

				if (i == j)			// 当i=j的时候 代表复制所有的"A" 肯定是在最小操作数的基础上复制，所以前面要纪录最小值
					dp[i][j] = minNum + 1;	

			}
		}
		return dp[n][n]-1;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/796180