Hexo

点滴积累 豁达处之

0%

leetcode算法-动态规划、回溯

Posted on Edited on In
LeetCode

leetcode算法

动态规划

定义

在现实生活中，有一类活动，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。

所以如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策，每一个阶段都有若干个策略可供选择，一个阶段的策略确定以后，形成了本阶段的决策，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。

当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。在多阶段决策问题中，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。

分析

5kg的袋子

物品：

钱：6 10 12

Kg：1 2 4

我们把5kg的袋子，拆分成1kg，1kg这样子计算，里面的表格就表示当前重量下能装的最多的钱。表格的数列就表示是要装的物品

Leetcode_114

加入物品2时，袋子当前为1kg 的容量时，我们发现物品2装不进去。那我们应该取多少呢？是不是只要取物品进来时1kg最大钱？，当袋子为2kg时，我们发现物品2可以装下去，此时可以得到10块钱，之前物品1进来时2kg最大是6吧，那我们肯定要选择大的这个10，而不是6.此时袋子还剩0kg可以装。

袋子为3kg时，我们还是可以装下这个物品2,得到10块，袋子还剩下1kg。10+1kg能装的东西。

物品3来了，袋子为4kg时，物品3可以转进来，得到12块钱，袋子还剩0kg。

我发现我不装物品3 还能得到16呢

物品3来了，袋子为5kg时，物品3可以转进来，得到12块钱，袋子还剩1kg。那么装了物品3就能得到12+6=18钱

我发现我不装物品3 能得到16，比18小，所以决定装。

图示(公式)

上面这一个递推过程总结起来就是一个东西——状态转移方程：

能装的时候 每次和上面的比较，大我就装，否则就不装。

Max(money[i]+res[i-1][w-weight[i]],res[i-1][w]);

1
2
3
4
money[i]+res[i-1][w-weight[i]]:装这个物品
w-weight[i] :表示装完还剩下的空间
res[i-1][w-weight[i]]:表示装完后剩下的空间还能装的最大值，取上一次的结果。
Res[i-1][w]表示不装这个物品的值

Leetcode_115

动态规划的阶梯步骤

  • 确定状态转移公式，当前的状态是怎么由前面的状态变化而来的及其与之相关的辅助的dp数组， （dp table）以及下标的含义。这一步往往也是最难的， 这一步清楚了，整个动态规划的问题基本上可以说就解决了一大半。一般来说，首先要确定dp数组中元素代表的意义，然后在这个意义之下，确定状态是如何在dp数组的元素之间如何变化的。
  • 初始化dp数组
  • 根据题目条件确定遍历顺序，并实现状态转移公式

代码

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
public class Dp {

 // 二维数组
    public static void main(String[] args) {
        int value [] ={60,100,120};
        int weigth[] = {10,20,40};	//购物车那个问题 只需要一个价值就行了，重量都都没有。

        int w = 50;
        int n = 3;
        // 声明二维数组表示物品与重量的最优方案
        int[][] dp = new int[n + 1][ w + 1];
        // 商品数量增加的最优解
        for(int i = 1; i <= n; i++){
            // 容量递增
            for(int j = 1; j <= w; j++){
                // 当前商品的重量 小于 指定重量 表示可以放
                int wei = weigth[i - 1];
                if(wei <= j){
                    // 上一行， 同列的值
                    int pre = dp[i - 1][weigth[i - 1] ];
                    // 当前物品 加剩余物品的值
                    int curr = value[i - 1] + dp[i - 1][j - wei];
                    dp[i][j] = Math.max(pre, curr);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        System.out.println(dp[n + 1][w + 1]);
    }
    
    
    // 一维数组
     public static void main(String[] args) {
        int value [] ={60,100,120};
        int weigth[] = {10,20,40};

        int w = 50;
        int n = 3;
        int[] dp = new int[ w + 1];
        for(int i = 0; i < n; i++){
            for(int j = w; j  > 0; j--){
                if(j>= weigth[i]){
                    int pre = dp[j - weigth[i]] + value[i];
                    int curr = dp[j];
                    dp[j] = Math.max(pre, curr);
                }
            }
        }
    }
}

**(LeetCode-53) **最大子序和

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

分析

方法1

既然是学习动态规划，我们当然用动态规划来求解。

首先确定状态转移公式，对于我们在遍历原始数组的过程中，每遇到一个元素nums[i]就要决定，这个元素是加入到当前连续子列，还是成为一个新连续子列的初始元素，所以状态转移公式可以这样描述，我们设当前连续子数组的和为sum，那么sumnew = max(nums[i],(sum+nums[i]))。

辅助的dp数组呢？用来存放每个阶段计算出来的连续子数组的和，每个元素dp[i]表示包括下标i之前的最大连续子序列和，也就是我们前面的sum，那么最终的状态转移公式就是dp[i]=max(nums[i],(dp[i-1]+nums[i]))。

对这个dp数组，按照题目，dp[0] = nums[0]。

Leetcode_116

注意最后的结果可不是dp[nums.size() - 1]。

在回顾下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。

那么我们要找最大连续子序列，就应该找每个i为终点的连续最大子序列。

这种方法的时间复杂度为O(n)，空间复杂度为O(n)。

方法2

但是其实仔细分析我们的代码，考虑到dp[i] 只和 dp[i-1] 相关，也就是说连这个dp数组都可以不用，我们可以用一个变量pre 来维护对于当前dp[i] 来说它的 dp[i-1] 的值是多少，从而让空间复杂度降低到 O(1)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MaxSubArray {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }

    public static int maxSubArray(int[] nums) {
        int result = nums[0];
        int pre = nums[0];
        for(int i = 1; i < nums.length; i++){
            int curr = nums[i];
            int premax = curr + pre;
            pre = Math.max(curr, premax);
            if(result < pre){
                result = pre;
            }
        }
        return result;
    }
}

(LeetCode-121)买卖股票的最佳时机

题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

分析

方法1

从实际的运行速度来看，动态规划的方法速度其实并不是那么快，有没有更快的方法呢？

其实分析题目我们可以发现，这其实就是个不断发现数组中的最小元素以及最小元素之后最大元素，进而计算最大差距，也就是利润的过程，在整个过程中最小元素可能会不断变化，最大差距自然也可能会发生变化，需要不断的更新最小元素和最大差距。所以整个过程如图示表示：

Leetcode_117

Leetcode_118

Leetcode_119

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class MaxProfit {

    public static void main(String[] args) {
        int[] nums = {2,4,1};
        System.out.println(maxProfit(nums));
    }

    public static int maxProfit(int[] prices) {
        int max = 0;  // 最大收益
        int indexPre = 0; //最大收益的买入点下标
        for(int i = 0; i < prices.length; i++){
            int pre = prices[i] - prices[indexPre];
            if(pre <= 0){
                indexPre = i;
            }else {
                if(max < pre){
                    max = pre;
                }
            }
        }
        return max;
    }
}

(LeetCode-470)用 Rand7() 实现 Rand10()

题目

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例 1:

1
2
输入: 1
输出: [2]

示例 2:

1
2
输入: 2
输出: [2,8]

示例 3:

1
2
输入: 3
输出: [3,8,10]

分析

方法一

思路与算法

我们可以用拒绝采样的方法实现 Rand10()。在拒绝采样中，如果生成的随机数满足要求，那么就返回该随机数，否则会不断生成，直到生成一个满足要求的随机数为止。

我们只需要能够满足等概率的生成 1010 个不同的数即可，具体的生成方法可以有很多种，比如我们可以利用两个 Rand7() 相乘，我们只取其中等概率的 1010 个不同的数的组合即可，当然还有许多其他不同的解法，可以利用各种运算和函数的组合等方式来实现。

  • 比如我们可以利用两个Rand7()相乘，分别可以得到结果如下：

Leetcode_120

  • 我们可以得到每个数生成的概率为:

Leetcode_121

  • 我们可以从中挑选 1010个等概率的数即可

题目中要求尽可能的减少 、Rand7() 的调用次数，则我们应该尽量保证生成的每个不同的数的生成概率尽可能的大，即调用 Rand7() 期望次数尽可能的小。

我们可以调用两次 Rand7()，那么可以生成 [1, 49][1,49] 之间的随机整数，我们只用到其中的前 4040 个用来实现 Rand10()，而拒绝剩下的 99 个数，如下图所示

Leetcode_122

我们可以看到表中的 [1,49][1,49] 每个数生成的概率为1 / 49

我们实际上只取 [1,40][1,40] 这前 40 个数，转化为 [1,10][1,10] 时，这 10 个数中每个数的生成概率则为4 / 49

代码

1
2
3
4
5
6
7
8
9
10
11
12
public static int rand10() {
     int temp = 40;
     while (temp >= 40){
         temp = (rand7() - 1) * 7 + rand7() - 1;
     }
     return temp % 10 + 1;
 }

 public static int rand7() {
     Random random = new Random();
     return random.nextInt(7) + 1;
 }

回溯

(LeetCode- 17) 电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

Leetcode2_19

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
输入：digits = ""
输出：[]

示例 3：

1
2
输入：digits = "2"
输出：["a","b","c"]

分析

方法一：回溯
首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。

回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。

回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

通过这个题目我们也能够整理出一个回溯算法大致的代码模板框架：

1
2
3
4
5
6
7
8
9
10
11
void backtrack(参数列表) {
    if (终止条件) {
    	存放结果;
   	 	return;
    }
    for (选择：本层集合中元素(树中节点孩子的数量就是集合的大小)) {
    	处理节点;
    	backtrack(新参数列表);  //递归处理当前节点下的子节点
    	回溯，撤销处理结果
    }
}

代码

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
public List<String> letterCombinations(String digits) {
       List<String> combinations = new ArrayList<String>();
       if (digits.length() == 0) {
           return combinations;
       }
       Map<Character, String> phoneMap = new HashMap<Character, String>() {{
           put('2', "abc");
           put('3', "def");
           put('4', "ghi");
           put('5', "jkl");
           put('6', "mno");
           put('7', "pqrs");
           put('8', "tuv");
           put('9', "wxyz");
       }};
       backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
       return combinations;
   }

   public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
   // 递归终止条件，将结果放入集合中
       if (index == digits.length()) {
           combinations.add(combination.toString());
       } else {
           char digit = digits.charAt(index);
           String letters = phoneMap.get(digit);
           int lettersCount = letters.length();
           // 遍历每个数字对应的字母表，也就是处理空间树中的非叶子节点
           for (int i = 0; i < lettersCount; i++) {
               combination.append(letters.charAt(i));
               // 继续处理下一个节点
               backtrack(combinations, phoneMap, digits, index + 1, combination);
               // 当前节点处理完成，往上回溯
               combination.deleteCharAt(index);
           }
       }
   }

(LeetCode- 22) 括号生成

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

1
2
输入：n = 1
输出：["()"]

分析

方法

这个题目我们依然可以先画出解空间树，再套用我们上个题目的代码模板来实现。我们用n=2来演示这个过程：

Leetcode2_20

这个题目相对于上一题《(LeetCode- 17) 电话号码的字母组合》，出现了剪枝的情况。因为根据题目要求，解空间树能出现右子树的情况，只有结果字符串中左括号的个数比右括号大的时候才可以。再结合回溯算法代码模板框架，这个题目就很容易处理了。我们依然直接使用LeetCode官方的代码。

代码

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
public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    /**
     * @param ans 结果集
     * @param cur 结果字符串， 完成后会加入结果集
     * @param open 左括号的已使用数量
     * @param close 有括号的已使用数量
     * @param max 最大数
     */
    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        // 左括号和有括号全部使用完毕， 递归终止，并将结果加入结果集中
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        // 处理左子树
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        // 处理右子树
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

(LeetCode- 39) 组合总和

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []

分析

方法

这个题目看起来比前面的17和22两个题都要复杂些，因为17和22两个题中备选元素只能选择一次，这里元素是可以重复选择的，但是其实对解题并没有影响。

同样的，我们可以先整理出解空间树再套用代码模板，不过这里的解空间树有两种处理方式，加减两种。

第一种，加法类型，我们以示例2，candidates = [2,3,5], target = 8来说明：

Leetcode2_21

通过上图我们可以看到，递归的终止条件就是累加和大于等于target ，大于的情况下，这个结果应该抛弃；等于的情况下则加入最终结果集，所以根据上图[2,2,2,2],[2,3,3],[3,5]，这三条路径就是我们需要的结果。

同时要注意，在进行分支的时候，取2分支会在[2,3,5]中取数，而取3分支则是在[3,5]中取数，取5分支则是在[5]中取，这是为了避免重复计算，如果取3或者取5分支下加入取2的选项，必然会和取2分支下的取3和取5选项出现重复。取5分支下没有取3的选项也是一样的道理。这同样是一种剪枝。具体的代码我们就不实现了。

第二种，减法类型，我们以示例1，candidates = [2,3,6,7], target = 7来说明：

Leetcode2_22

我们以需要的target = 7为根结点，创建分支做减法操作；每一个箭头表示：从父亲结点的数值减去边上的数值，得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值；

减到0或者负数的时候停止，也就是递归的终止条件，而减到0则是我们需要的结果。所以，根据上图可以得到的结果集有[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]，但是和示例1的答案[7], [2, 2, 3]比较，很明显我们的结果集里有重复的，因为题目中要求每一个符合要求的解是组合，也就是不计算顺序的。

所以我们在减法类型的处理里，需要和加法类型一样，去除重复计算，比如减2操作，就应该只在减2分支中出现，在减3、6、7分支中都不应该出现。

Leetcode2_23

代码

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
public static void main(String[] args) {
       int[] candidates = {1,2,3,6,7};
       List<List<Integer>> result = new CombinationSum().combinationSum( candidates,  7);
       System.out.println("");
   }

   public List<List<Integer>> combinationSum(int[] candidates, int target) {
       List<List<Integer>> ans = new ArrayList<>();
       backtrack(ans, new ArrayList<Integer>(), candidates, target,  0);
       return ans;
   }

   private void backtrack(List<List<Integer>> ans, ArrayList<Integer> integers, int[] candidates, int target,  int start) {
       if(start == candidates.length) {
           return;
       }
       if(target == 0){
           ans.add(new ArrayList<Integer>(integers));
           return;
       }
       // 直接跳过
       backtrack(  ans, integers,candidates, target,start + 1);
       // 选择当前数
       if((target - candidates[start]) >= 0){
           integers.add(candidates[start]);
           backtrack( ans,  integers,  candidates,  target - candidates[start],  start);
           integers.remove(integers.size() -1);
       }
   }

(LeetCode- 46) 全排列

题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[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
public class Permute {

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        List<List<Integer>> result = new Permute().permute( nums);
        System.out.println("");
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int[] used = new int[nums.length];
        backtrack(ans, nums, new ArrayList<Integer>(),used );
        return ans;
    }

    private void backtrack(List<List<Integer>> ans, int[] nums, ArrayList<Integer> integers, int[] used ) {
        if(integers.size() == nums.length){
            ans.add(new ArrayList<>(integers));
            return;
        }
        for(int i = 0; i < nums.length; i++){
               // 当前节点在祖先节点已经使用过， 不再参与子孙节点的处理
            if(used[i] == 1) continue;
            //标识当前元素已经使用
            used[i] = 1;
            integers.add(nums[i]);
            backtrack(ans, nums, integers, used);
            //回溯
            used[i] = 0;
            integers.remove(integers.size()-1);
        }
    }
}

(LeetCode- 47) 全排列 II

题目

给定一个可包含重复数字的序列 nums ，**按任意顺序** 返回所有不重复的全排列。

示例 1：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,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
public static void main(String[] args) {
       int[] nums = {1,1,2};
       List<List<Integer>> result = new Permute().permuteUnique( nums);
       System.out.println("");
   }

   public List<List<Integer>> permuteUnique(int[] nums) {
       List<List<Integer>> ans = new ArrayList<>();
       int[] used = new int[nums.length];
       Arrays.sort(nums);
       backtrack(ans, nums, new ArrayList<Integer>(),used );
       return ans;
   }

   private void backtrack(List<List<Integer>> ans, int[] nums, ArrayList<Integer> integers, int[] used ) {
       if(integers.size() == nums.length){
           ans.add(new ArrayList<>(integers));
           return;
       }
       for(int i = 0; i < nums.length; i++){
              // 当前节点在祖先节点已经使用过， 不再参与子孙节点的处理
           if(used[i] == 1) continue;
           // 判断是否重复处理了， !(used[i-1]==1) 用来保证这个判断是同层判定， 而不是子节点判定
           if((i > 0) && nums[i] == nums[i-1] && !(used[i-1] == 1)) continue;
           //标识当前元素已经使用
           used[i] = 1;
           integers.add(nums[i]);
           backtrack(ans, nums, integers, used);
           //回溯
           used[i] = 0;
           integers.remove(integers.size()-1);
       }
   }

(LeetCode- 78) 子集

题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

代码

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
public class Subsets {

    public static void main(String[] args) {
      //  int[] nums = {1,2,3};
        int[] nums = {0};
        List<List<Integer>> list = new Subsets().subsets(nums);
        System.out.println("");
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack( ans,   new ArrayList<Integer>(),  nums, 0);
        return ans;
    }

    private void backtrack(List<List<Integer>> ans, ArrayList<Integer> integers, int[] candidates, int index) {
        ans.add(new ArrayList<Integer>(integers));

        for(int i = index; i < candidates.length; i++){
            integers.add(candidates[i]);
            backtrack(ans,  integers,  candidates, i + 1);
            integers.remove(integers.size()-1);
        }

    }
}

(LeetCode- 79) 单词搜索

题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

Leetcode2_24

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

Leetcode2_25

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

Leetcode2_26

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

代码

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
public class Exist {
    public boolean exist(char[][] board, String word) {
        char[] w = word.toCharArray();
        for (int x=0; x<board.length; x++) {
            for (int y=0; y<board[x].length; y++) {
                if (backTrack(board, x, y, w, 0)) return true;
            }
        }
        return false;
    }

    private boolean backTrack(char[][] board, int x, int y, char[] word, int currLength) {
        if (currLength == word.length) return true;
        /*矩阵越界检查*/
        if (x<0 || y<0 || x == board.length || y == board[x].length) return false;
        if (board[x][y] != word[currLength]) return false;
        /*当前元素进行异或用来标识已经访问过
         * char在Java中默认是两个字节，所以不会有位溢出风险*/
        board[x][y] ^= 256;
        /*按照右、下、左、上的顺序进行试探*/
        boolean exist = backTrack(board, x, y+1, word, currLength+1)
                || backTrack(board, x-1, y, word, currLength+1)
                || backTrack(board, x+1, y, word, currLength+1)
                || backTrack(board, x, y-1, word, currLength+1);
        /*回溯，再次异或,复原原来的元素值*/
        board[x][y] ^= 256;
        return exist;
    }
}

贪心算法

什么是贪心算法

贪心算法顾名思义在一个贪字上面，它在解决某个问题的时候，总是先从眼前利益出发。也就是说只顾眼前，不顾大局，所以它是局部最优解。它的核心的就是局部最优推出全局最优。

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿?指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

很明显在我们上面拿钞票的过程中，总是做出在当前看来是最好的选择并没有从整体钱最多上加以考虑。

贪心算法和我们前面的曾经学习过的动态规划非常的相似，但是两者还是有不同的，比如动态规划里常见的背包问题有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不一定行了。

动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解，也都有最优子结构的说法，但是贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留，每一步的最优解一定包含上一步的最优解。动态规划里的全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。有时候我们也会把贪心算法视为动态规划算法的一种特例。

总的来说贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法一般分为如下四步︰

将问题分解为若干个子问题；

找出适合的贪心策略

求解每一个子问题的最优解；

将局部最优解堆叠成全局最优解

但是真正做题的时候很难分出这么详细的解题步骤，而且贪心算法的问题简单题的甚至感觉不到贪心，但贪心的难题其实可以非常难。而且贪心算法不像回溯算法，贪心算法没有套路，也没有框架之类的，需要同学们多看多练培养感觉才能想到贪心的思路。

(LeetCode-621)任务调度器

题目

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

示例 1：

1
2
3
4
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

示例 2：

1
2
3
4
5
6
7
8
输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类

示例 3：

1
2
3
4
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
     A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeastInterval {

    public int leastInterval(char[] tasks, int n) {
        int[] arr = new int[26];
        // 统计各个字母出现的次数
        for(char c : tasks){
            arr[c - 'A']++;
        }

        int max = 0;
        // 找到最大次数
        for(int i = 0; i < 26; i++){
            max = Math.max(max, arr[i]);
        }
        int ret = (max - 1) * (n + 1);
        // 寻找最大次数相同的字母个数，然后累加进ret
        for(int i = 0; i < 26; i++){
            if(arr[i] == max){
                ret++;
            }
        }
        return Math.max(ret, tasks.length);
    }
}

(LeetCode- 62) 不同路径

题目

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

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

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

示例 1：

Leetcode2_27

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

示例 2：

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

示例 3：

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

示例 4：

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

分析

方法

这个题目看起来好像很麻烦，但是仔细想想，假设机器人已经到达了Finish位置，那么机器人怎么到达这个位置呢？因为题目规定“机器人每次只能向下或者向右移动一步”，所以只能从Finish位置的上面a或者左边b。

Leetcode2_28

自然，到达Finish位置的路径数=“到达a的路径数”+到达b的路径数”。在这个m x n 网格中，a和b的位置和Finish位置的关系是什么？

1
2
a的位置坐标 = [Finish位置行数-1，Finish位置列数]
b的位置坐标 = [Finish位置行数，Finish位置列数-1]

想明白这点，DP数组就已经出来了，我们定义DP数组为dp[i][j]，i和j表示当前元素在网格中的坐标，dp[i][j]表示到达当前元素的的路径数，状态转移公式：

1
dp[i][j] = dp[i-1][j] + dp[i][j-1]

DP数组的初始值呢？dp[0][0]=0，这是毫无疑问的，不过要注意，当i=0以及j=0时，到达的路径有几条？因为题目规定“每次只能向下或者向右移动”，所以这些单元格的路径只有一条，这些元素也可以作为DP数组的初始值。

具体实现看代码，这种实现，很明显，时间复杂度和空间复杂度都是O(m*n)。不过考察具体的过程，可以发现空间复杂度可以降低，因为从状态转移公式dp[i][j] = dp[i-1][j] + dp[i][j-1]，我们可以知道，dp[i][j-1]属于本行的数据，dp[i-1][j]是上一行的数据，我们完全可以利用一个一维数组来作为DP数组，比如示例1里，i=1，得到的dp一维数组值为：

Leetcode2_29

当我们要计算二维数组里i=2，j=4元素的值时，它的值放在一维数组里其实就是：dp[j]=dp[j]+dp[j-1]这样的话，空间复杂度就降为O(n)。

Leetcode2_30

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class UniquePaths {

    public static void main(String[] args) {
        int m = 3, n = 7;
        int i = new UniquePaths().uniquePaths(m, n);
        System.out.println("");
    }
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // 填充i 为0 的行
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++){
            dp[0][i] = 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];
    }
}

(LeetCode- **64) **最小路径和

题目

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

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

示例 1：

Leetcode2_31

1
2
3
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

1
2
输入：grid = [[1,2,3],[4,5,6]]
输出：12

分析

方法

这个题目和《(LeetCode- 62) 不同路径》有非常大的相似之处，思考的思路也非常相似，考虑当前到达右下角，哪条路径数字最小？只有两个选择，a和b：

1
2
a的位置坐标 = [右下角元素位置行数-1，右下角元素位置列数]
b的位置坐标 = [右下角元素位置行数，右下角元素位置列数-1]

Leetcode2_32

a和b选择谁呢？当然是a和b两者中路径数字最小的那个，注意，这里说“a和b两者中路径数字”并不是指a和b本身的值1和2，而是指到达a和b的路径和，只不过在示例1里恰好a本身的值比b本身的值小而已。右边的结果推导图已经说明了这一点。
很明显，我们定义DP数组为dp[i][j], i和j表示当前元素在网格中的坐标，dp[i][j] 表示到达当前元素的的最小路径数，状态转移公式：

1
dp[i][j] = 原始数组[i][j]+min(dp[i-1][j],dp[i][j-1])

DP数组的初始值呢？dp[0][0]=grid[0][0] 这是毫无疑问的，而且当i=0时，数组的值只能从左边元素获得；j=0时，数组的值只能从上边元素获得，这些元素都可以作为DP数组的初始值。时间复杂度和空间复杂度都是O(m*n)

与《(LeetCode- 62) 不同路径》类似，考察具体的过程，可以发现空间复杂度可以降低，因为从状态转移公式原始数组[i][j]+min(dp[i-1][j],dp[i][j-1])，我们可以知道，dp[i][j-1]属于本行的数据，dp[i-1][j]是上一行的数据，我们完全可以利用一个一维数组来作为DP数组，比如示例1里，i=1，得到的dp一维数组值为：

Leetcode2_33

当我们要计算二维数组里i=2，j=2元素的值时，它的值放在一维数组里其实就是：原始数组[i][j]+min(dp[j],dp[j-1])。这样的话，空间复杂度就降为O(n)。

Leetcode2_34

代码

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
public class MinPathSum {

    public static void main(String[] args) {
        int[][] grid = {{1,3,1}, {1,5,1}, {4,2,1}};
        new MinPathSum().minPathSum(grid);
        System.out.println("");
    }

    public int minPathSum(int[][] dp) {
        int m = dp.length, n = dp[0].length;
        // 填充i 为0 的行
        for(int i = 1; i < m; i++){
            dp[i][0] = dp[i][0] + dp[i-1][0];
        }
        for(int i = 1; i < n; i++){
            dp[0][i] = dp[0][i] + dp[0][i - 1];
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m - 1][n-1];
    }
}

(LeetCode- **91) **解码方法

题目

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

1
2
3
4
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

1
2
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

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

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

示例 1：

1
2
3
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

1
2
3
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

1
2
3
4
5
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

分析

方法

我们用示例2来看看：226解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6)

Leetcode2_35

可以看到，在遍历原始字符串的过程中，除了需要考虑当前字符能否满足映射关系，往往还需要考虑当前字符能否前面的字符组合并且满足映射关系。

我们用动态规划来解决这个问题，首先对DP数组来说，我们定义数组为dp[i]，i表示了当前已经遍历了几个原始字符串中的字符，这就是说i是从1开始的，通过i定位原始字符串中的字符时，对应的下标就需要减1，dp[i]表示到达DP数组当前元素时的解码总数，那状态转移公式呢？这个就需要仔细想想了。

如果当前字符不等于字符’0’，当前字符本身是能满足映射关系的，这属于一种解码方式（可以理解为所有字符都能单独解码）这种情况下，解码i个字符和解码i-1个字符的解码数是一样的，也就是dp[i] = dp[i-1]

Leetcode2_36

除此之外，当前字符还能和前面的字符组合起来满足映射关系，但是有限制条件，就是组成的数字在10~26之间，这种情况下，解码i个字符和解码i-2个字符的解码数是一样的，也就是dp[i] = dp[i-2]。

Leetcode2_37

所以，完全的状态转移公式是：

1
dp[i] = dp[i-1] + dp[i-2]

Leetcode2_38

这个DP数组的初始值呢？我们前面说过“i表示了当前已经遍历了几个原始字符串中的字符，i是从1开始的”，i=0则表示前0个数字的方案数，这个没有任何实际的意义，但是dp[0]的值需要保证边界是对的，即dp[1]和dp[2]是对的。

比如说，第一个数不为0，那么解码前1个数只有一种方法，将其单独解码，即dp[1] = dp[1 - 1] = 1。解码前两个数，如果第1个数和第2个数可以组合起来解码，那么dp[2] = dp[1] + dp[0] = 2 ，否则只能单独解码第2个数，即dp[2] = dp[1] = 1。因此，在任何情况下dp[0]取1都可以保证dp[1]和dp[2]是正确的，所以初始值我们设置dp[0]=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
public class NumDecodings {

    public static void main(String[] args) {
        String s = "291";
        int i = new NumDecodings().numDecodings(s);
        System.out.println("");
    }

    public int numDecodings(String s) {
        int n = s.length();
        /*取代DP数组的变量，类似于滚动数组
         * pre = 1 起到了类似DP数组初始化的作用*/
        int prePre = 0, pre = 1, curr = 0;
        /*DP数组中i是从1开始的，通过i定位原始字符串中的字符时，对应的下标就需要减1*/
        for (int i = 1; i <= n; ++i) {
            curr = 0;
            /*当前字符单独映射*/
            if (s.charAt(i - 1) != '0')   curr += pre;
            /*原始字符串当前元素i-1可以和前面的元素i-2组合满足映射关系*/
            if (i >= 2) {
                /*元素的组合转为数字*/
                int num = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
                if (num >= 10 && num <= 26) curr += prePre;;
            }
            /*更新变量的值，为下个元素做准备*/
            prePre = pre;
            pre = curr;
        }
        return curr;
    }
}

(LeetCode- 198) 打家劫舍

题目

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

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

示例 1：

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

示例 2：

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

分析

状态转移公式

1
dp[i] = max(nums[i] + dp[i-2],dp[i-1])

初始化：

1
2
dp[0] = 数组第一个
dp[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
public class Rob {

    public static void main(String[] args) {
       // int[] nums = {1,2,3,1};
        int[] nums = {2,7,9,3,1};
        int i = new Rob().rob(nums);
        System.out.println("");
    }
    public int rob(int[] nums) {
        int max = 0;
        int[]  dp = new int[nums.length];
        if(nums.length == 1){
            return nums[0];
        }
        dp[0] = nums[0];
        max = Math.max(nums[0], nums[1]);
        if(nums.length == 2){
            return max;
        }
        dp[1] = max;

        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1] , nums[i] + dp[i - 2]);
        }
        return dp[nums.length-1];
    }
}

(LeetCode- 300) 最长递增子序列

题目

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

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

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class LongestIncrSubseq_300 {

    /*标准DP实现*/
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /*二分查找+DP实现*/
    public int lengthOfLIS3(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        /*因为dp数组中没有存放子序列的长度，需要我们单独统计
         * 用变量记录当前dp数组包含有效元素的实际长度*/
        int result = 1;
        dp[0] = nums[0];
        for(int i = 1 ;i < length;i++){
            if(nums[i] > dp[result-1]){
                dp[result] = nums[i];
                result++;
            }else{
                /*start和end指明了当前dp数组有效元素的起止位置*/
                int start = 0, end = result;
                /*以二分查找在dp数组中寻找第1个大于number的元素*/
                while(start < end) {
                    int m = (start + end) / 2;
                    if(dp[m] < nums[i])
                        start = m + 1;
                    else
                        end = m;
                }
                /*替换dp数组中的元素*/
                dp[start] = nums[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        new LongestIncrSubseq_300().lengthOfLIS3(new int[]{10,9,2,5,3,7,101,18});
    }
}

(LeetCode- 309) 最佳买卖股票时机含冷冻期

题目

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。

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

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

示例 1:

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

示例 2:

1
2
输入: prices = [1]
输出: 0

分析

方法

我们曾在第二期中分析过《(LeetCode-121) 买卖股票的最佳时机》，这个题目相对121，新增了一个冷冻期，但是基本的处理思想并没有变。

仔细思考一下，对某天来说，可能存在的状态以及对应的动作，无非就是下面几种：

Leetcode2_39

比如“未动作/不持有”，说明当天没做任何买卖股票的动作，而且也不持有股票。

从第i-1天到第i天的变化的可能性有哪些呢？

Leetcode2_40

比如第i-1天是因为买入而持有的状态，到了第i天只能变为卖出/不持有和(曾经)买入/持有，因为1、从“买入/持有到”到“未动作/不持有”这是不可能的变化，2、从“买入/持有”到“冷冻期/不持有”，这也是不可能的变化。

理清了上面的状态变化关系，我们就可以定义一个二维DP数组dp[i][j=4]，对于某个确定的dp[i][j]元素来说，下标i表示第i天能获得的最大利润，可正可负；下标j表示当天持有股票的状态，0表示卖出/不持有，1表示未动作/不持有，2表示(曾经)买入/持有，3表示冷冻期/不持有。状态转移公式呢？其实从上图就能看出来了：

1
2
3
4
dp[i][0] = prices[i]+dp[i-1][2]
dp[i][1] = max(dp[i-1][1],dp[i-1][3])
dp[i][2] = max(dp[i-1][1]-prices[i],dp[i-1][2],dp[i-1][3]-prices[i])
dp[i][3] = dp[i-1][0]

在我们遍历完原始数组，并填充完dp数组后，最终的结果就应该选取3个不持有的最大值。

dp数组的初始值，就只需要考虑第0天的情况，很明显：

1
2
3
4
dp[0][2] = -nums[0]
dp[0][1] = 0
dp[0][0] = 0
dp[0][3] = 0

很明显，这种方法的时间复杂度和空间复杂度都是O(n)，当然从我们前面的描述和代码实现来看，其实dp[i]之和dp[i-1]有关，所以可以将空间复杂度降为O(1)，这个就作为思考题，大家自行实现，提示：将dp数组声明为dp[2][4]大小是一种解决方案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices) {
        int length = prices.length;
        int[][] dp = new int[length][4];
        dp[0][2] = -prices[0];
        for(int i = 1; i < length; i++){
            dp[i][0] = prices[i]+dp[i-1][2];
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]);
            dp[i][2] = Math.max(dp[i-1][1]-prices[i],Math.max(dp[i-1][2],dp[i-1][3]-prices[i]));
            dp[i][3] = dp[i-1][0];
        }
        return Math.max(dp[length-1][0],Math.max(dp[length-1][1],dp[length-1][3]));
    }

    public static void main(String[] args) {
        new BuyStockWithCooldown_309().maxProfit(new int[]{1,2,3,0,2});
    }

(LeetCode- **322) **零钱兑换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

示例 1：

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

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0

分析

方法二：动态规划

算法

我们采用自下而上的方式进行思考。仍定义 F(i) 为组成金额 ii 所需最少的硬币数量，假设在计算 F(i) 之前，我们已经计算出 F(0)−F(i−1) 的答案。 则 F(i) 对应的转移方程应为

Leetcode2_41

其中 cj 代表的是第 j 枚硬币的面值，即我们枚举最后一枚硬币面额是 cj ，那么需要从 i−cj 这个金额的状态 F(i−cj) 转移过来，再算上枚举的这枚硬币数量 1 的贡献，由于要硬币数量最少，所以 F(i) 为前面能转移过来的状态的最小值加上枚举的硬币数量 1 。

例子1：假设

1
coins = [1, 2, 5], amount = 11

则，当 i*==0 时无法用硬币组成，为 0 。当 i<0 时，忽略 F(i)

F(i) 最小硬币数量
F(0) 0 //金额为0不能由硬币组成
F(1) 1 //F(1)=min(F(1-1),F(1-2),F(1-5))+1=1
F(2) 1 //F(2)=min(F(2-1),F(2-2),F(2-5))+1=1
F(3) 2 //F(3)=min(F(3-1),F(3-2),F(3-5))+1=2
F(4) 2 //F(4)=min(F(4-1),F(4-2),F(4-5))+1=2
… …
F(11) 3 //F(11)=min(F(11-1),F(11-2),F(11-5))+1=3

我们可以看到问题的答案是通过子问题的最优解得到的。

例子2：假设

1
coins = [1, 2, 3], amount = 6

Leetcode2_42

在上图中，可以看到：

Leetcode2_43

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int coinChange(int[] coins, int amount) {
      int max = amount + 1;
      int[] dp = new int[amount + 1];
      Arrays.fill(dp, max);
      dp[0] = 0;
      for (int i = 1; i <= amount; i++) {
          for (int j = 0; j < coins.length; j++) {
              if (coins[j] <= i) {
                  dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
              }
          }
      }
      return dp[amount] > amount ? -1 : dp[amount];
  }

(LeetCode-406) 根据身高重建队列

题目

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

1
2
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

分析

方法二：从高到低考虑

思路与算法

我们可以将每个人按照身高从大到小进行排序，处理身高相同的人使用的方法类似，即：按照 hi 为第一关键字降序，ki 为第二关键字升序进行排序。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 i 个人时：

  • 第 0, i−1 个人已经在队列中被安排了位置，他们只要站在第 i 个人的前面，就会对第 i 个人产生影响，因为他们都比第 i 个人高；

  • 而第 i+1, n−1 个人还没有被放入队列中，并且他们无论站在哪里，对第 i 个人都没有任何影响，因为他们都比第 i 个人矮。

在这种情况下，我们无从得知应该给后面的人安排多少个「空」位置，因此就不能沿用方法一。但我们可以发现，后面的人既然不会对第 i 个人造成影响，我们可以采用「插空」的方法，依次给每一个人在当前的队列中选择一个插入的位置。也就是说，当我们放入第 i 个人时，只需要将其插入队列中，使得他的前面恰好有 ki 个人即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[][] reconstructQueue(int[][] people) {
       Arrays.sort(people, (o1, o2) -> {
           if(o1[0] != o2[0]){
               return o2[0] - o1[0];
           }else {
               return  o1[1] - o2[1];
           }
       });

       List<int[]> answer = new ArrayList<>();
       for(int[] element : people){
           answer.add(element[1], element);
       }
       return answer.toArray(new int[answer.size()][]);
   }

(LeetCode- **337) **打家劫舍Ⅲ

题目

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

Leetcode2_44

1
2
3
输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

Leetcode2_45

1
2
3
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

分析

方法

在前面我们已经分析过《(LeetCode- 198) 打家劫舍》，这个题目和198的差别在哪里？198中需要处理的数据是数组的形式呈现的，而这个题目的数据是个二叉树的数据结构。这个题目就是个典型的树形DP的问题。

我们来分析下这个题目的解题思路，使用下图所示的二叉树来说明，为了方便说明我们给每个节点加上了诸如a,b，c之类的标识。

Leetcode2_46

可以确定的是，对这个树一定要遍历，对树的遍历用递归比较方便，但是树的遍历有前、中、后、层至少四种遍历方式（不记得怎么遍历的同学，应该回过头去看看一期里的相关知识），应该用哪种呢？我们现在无法确定，先不急，后面随着分析的深入，也许我们就知道答案了。

按照题目要求“两个直接相连的房子不能在同一天晚上被打劫”，在树里面什么节点是直接相连的？父节点和它的两个左右子节点，这就是说在遍历树的时候，访问节点的值，偷了父节点就不能偷它的两个左右子节点，反过来说也成立，偷了节点的左右子节点就不能偷这个节点本身。但是偷了左节点，右节点还是可以继续偷，这个要注意。

我们先不要看整颗树，只看由b、d、e三个节点组成的子树：

Leetcode2_47

按照我们上面的说明，b、d、e三者之中，要么偷b，要么不偷b而是偷d和e，到底偷谁呢？当然是谁大偷谁。按照树的遍历，如果是前序和中序，都会出现不知道子节点值是多少的问题，只有后序遍历是先访问完两个左右子树再访问根结点的，所以这里我们确定了，对树的遍历用后序遍历会更方便。

现在问题来了，偷b的时候，怎么知道b能不能偷，值不值的偷呢？因为偷b不仅取决于d和e的值，还取决于d和e有无子树，同时偷b也会影响节点a的处理。这个时候我们就要站在整树的角度来考虑这个问题了。

对于树中的任何一个节点X，对它的访问应该返回一个复合结果，包含两种结果：

1
2
a.偷X时以X为根结点的子树返回的最大值
b.不偷X时以X为根结点的子树返回的最大值

这样的话，我们可以使用一个长度为2的数组dp表示节点X的返回值，dp[0]表示偷X时的最大值，dp[1]表示不偷X时的最大值。更具体点，我们用节点b来说明。

后序遍历了b的d和e两个子节点后，d和e各返回一个结果数组dp_d和dp_e，对于节点b来说，它的结果数组dp_b的值如下图所示：

Leetcode2_48

也就是偷b时的值是 b本身的值+不偷d的最大值（dp_d[1]）+不偷e的最大值（dp_e[1]）；如果不偷b，则值为max(dp_d[0],dp_d[1]) + max(dp_e[0],dp_e[1])。

然后，我们将b结果数组dp_b，作为b节点的结果返回供节点a的进行处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int rob(TreeNode root) {
       int[] result = robNode(root);
       return Math.max(result[0], result[1]);
   }

   // 返回值表示当前节点root的结果， 用长度为2的数组表示
   // 下标[0] 表示偷 root时的最大值， 下标[1]表示不偷root时的最大值
   private int[] robNode(TreeNode root) {
       // 已经处理到了叶子节点的下层， 递归终止
       if(root == null) return new int[]{0,0};
       // 当前root节点的左子节点处理结果
       int[] left = robNode(root.left);
       // 当前root节点的右子节点处理结果
       int[] right = robNode(root.right);
       // 偷当前节点root时的值是
       // root 本身 + 不偷左子节点的最大值 + 不偷右子节点的最大值
       int stealCurr = root.val + left[1] + right[1];
       //不偷当前节点root的值是
       // 偷左子节点 和不偷左子节点的值 两者的最大值 + 偷右子节点和不偷右子节点的值 两者的最大值
       int noStealCurr = Math.max(left[0] , left[1]) + Math.max(right[0], right[1]);
       return  new int[]{stealCurr, noStealCurr};
   }

(LeetCode- **416) **分割等和子集

题目

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

分析

方法一：动态规划
思路与算法

这道题可以换一种表述：给定一个只包含正整数的非空数组 \textit{nums}[0]nums[0]，判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半。因此这个问题可以转换成「0-10−1 背包问题」。这道题与传统的「0-10−1 背包问题」的区别在于，传统的「0-10−1 背包问题」要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。类似于传统的「0-10−1 背包问题」，可以使用动态规划求解。

在使用动态规划求解之前，首先需要进行以下判断。

  • 根据数组的长度 n 判断数组是否可以被划分。如果 n<2，则不可能将数组分割成元素和相等的两个子集，因此直接返回 false。
  • 计算整个数组的元素和 sum 以及最大元素 maxNum。如果 sum 是奇数，则不可能将数组分割成元素和相等的两个子集，因此直接返回 false。如果 sum 是偶数，则令 target= sum / 2，需要判断是否可以从数组中选出一些数字，使得这些数字的和等于 target。如果 maxNum>target，则除了 maxNum 以外的所有元素之和一定小于 target，因此不可能将数组分割成元素和相等的两个子集，直接返回 false。

创建二维数组 dp，包含 n 行 target+1 列，其中dp[i][j]表示从数组的[0, i]下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，dp 中的全部元素都是 false。

在定义状态之后，需要考虑边界情况。以下两种情况都属于边界情况。

  • 如果不选取任何正整数，则被选取的正整数等于 0。因此对于所有 0≤i<n，都有 dp[i][0] = true
  • 当 i==0 时，只有一个正整数 nums[0] 可以被选取，因此 dp[0][nums[0]] = true

对于 i>0 且 j>0 的情况，如何确定dp[i][j]的值？需要分别考虑以下两种情况。

  • 如果 j≥nums[i]，则对于当前的数字 nums[i]，可以选取也可以不选取，两种情况只要有一个为 true，就有 dp[i][j] = true

    • 如果不选取 nums[i]，则 dp[i][j] = dp[i - 1][j]
    • 如果选取nums[i]，则 dp[i][j] = dp[i - 1][j - nums[i]]

  • 如果 j<nums[i]，则在选取的数字的和等于 j 的情况下无法选取当前的数字 nums[i]，因此有 dp[i][j] = dp[i - 1][j]

状态转移方程如下：

Leetcode2_49

上述代码的空间复杂度是 O(n×target)。但是可以发现在计算 dp 的过程中，每一行的 dp 值都只与上一行的 dp 值有关，因此只需要一个一维数组即可将空间复杂度降到 O(target)。此时的转移方程为：

Leetcode2_50

且需要注意的是第二层的循环我们需要从大到小计算，因为如果我们从小到大更新 dp 值，那么在计算 dp[j] 值的时候，dp[j−nums[i]] 已经是被更新过的状态，不再是上一行的 dp 值。

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
public class CanPartition {

    public static void main(String[] args) {
        int[] nums = {1,5,11,5};
        boolean b = new CanPartition().canPartition(nums);
        System.out.println("");
    }

    // 一维数组
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = target; j >= num; --j) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }

    // 二维数组
    public boolean canPartition3(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }
}

(LeetCode- 494)目标和

题目

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
    返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

1
2
输入：nums = [1], target = 1
输出：1

分析

方法二：动态规划
记数组的元素和为 sum，添加 - 号的元素之和为 neg，则其余添加 + 的元素之和为 sum−neg，得到的表达式的结果为

Leetcode2_51

由于数组 nums 中的元素都是非负整数，neg 也必须是非负整数，所以上式成立的前提是 sum−target 是非负偶数。若不符合该条件可直接返回 0。

若上式成立，问题转化成在数组nums 中选取若干元素，使得这些元素之和等于 neg，计算选取元素的方案数。我们可以使用动态规划的方法求解。

定义二维数组 dp，其中dp[i][j]表示在数组nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数。假设数组nums 的长度为 n，则最终答案为 dp[n][neg]

当没有任何元素可以选取时，元素和只能是 0，对应的方案数是 1，因此动态规划的边界条件是：

Leetcode2_52

Leetcode2_53

由于dp 的每一行的计算只和上一行有关，因此可以使用滚动数组的方式，去掉 dp 的第一个维度，将空间复杂度优化到 O(neg)。

实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是dp[i - 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class FindTargetSumWays {

    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1};
        int targetSumWays = new FindTargetSumWays().findTargetSumWays2(nums, 3);
        System.out.println("");
    }

// 一维数组
    public int findTargetSumWays2(int[] nums, int target) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        int diff = sum - target;
        if(diff < 0 || diff % 2 != 0){
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[] dp = new int[neg + 1];
        dp[0] = 1;
        for(int num : nums){
            for(int j = neg; j >= num; j--){
                dp[j] = + dp[j] + dp[j-num];
            }
        }
        return dp[neg];
    }

// 二维数组
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        int diff = sum - target;
        if(diff < 0 || diff % 2 != 0){
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            int num = nums[i-1];
            for(int j = 0; j <= neg; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= num){
                    dp[i][j] += dp[i-1][j-num];
                }
            }
        }
        return dp[n][neg];
    }
}

(LeetCode- **718) **最长重复子数组

题目

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

1
2
3
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

1
2
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

分析

方法一：动态规划

对这个题目，我们可以定义DP数组为二维的，也就是dp[i][j]其中的每个元素dp[i][j]表示，以下标i-1为结尾的数组nums1 ，和以下标j-1为结尾的数组nums2，当前的最长重复子数组长度填充在这个元素dp[i][j]中。

状态转移公式呢？如果nums1[i-1]和nums2[j-1]的数字相等，dp[i][j]的值就要在前一dp元素的基础上加1，表示最长重复子数组长度要加1。问题是和谁相加呢？我们用示例1：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]来说说明。

Leetcode2_54

现在，nums1[3] = nums2[1]，那就是dp[4][2]需要在前一dp元素的基础上加1，从图上我们可以看出，dp[4][2]的前一元素应该是dp[3][1]。对应着nums1[2] = nums2[0]=3

所以状态转移公式就是：

1
如果(nums1[i-1] = nums2[j-1]) 那么dp[i][j] = dp[i-1][j-1] + 1

dp数组的初始值应该设定为dp[0][0] = dp[i][0] = dp[0][j] = 0，这个并没有什么实际意义，只是为了满足我们上面的状态转移公式。

当然，从状态转移公式可以看出，其实dp[i][j]只和dp[i-1][j-1]相关，所以可以使用一维数组，在处理dp[i]时直接使用上一次循环中填充在dp数组的dp[i-1]相关的值，将空间复杂度降为O(m)，但是在具体实现时要记得j要变成倒序遍历，以及当nums1[i-1] <> nums2[j-1]时，dp[i][j]要置为0（避免dp[i][j]的值影响dp[i+1][j+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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class FindLength {

    public static void main(String[] args) {
        int[] num1 = {1,2,3,2,1};
        int[] num2 = {3,2,1,4,7};
        int length2 = new FindLength().findLength(num1, num2);
        System.out.println("");
    }

    // 一维数组
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int[] dp = new int[len2 + 1];
        int max = 0;
        // 初始化
        dp[0] = 0;
        for(int i = 1; i <= len1; i++){
            int num1 = nums1[i-1];
            for(int j = len2; j >= 1; j--){
                int num2 = nums2[j-1];
                if(num1 == num2){
                    dp[j] = dp[j-1] + 1;
                }else {
                    dp[j] = 0;
                }
                max = Math.max(max, dp[j]);
            }
        }
        return max;
    }

    // 二维数组
    public int findLength2(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];
        int max = 0;
        // 初始化
        for(int i = 0; i <= len1; i++){
            dp[len1][0] = 0;
        }
        for(int i = 0; i <= len2; i++){
            dp[0][len2] = 0;
        }
        for(int i = 1; i <= len1; i++){
            int num1 = nums1[i-1];
            for(int j = 1; j <= len2; j++){
                int num2 = nums2[j-1];
                if(num1 == num2){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = 0;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}

(LeetCode- **42) **接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

Leetcode2_55

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

分析

方法一：动态规划

Leetcode2_56

Leetcode2_57

代码

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
public class Trap {

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        int trap = new Trap().trap(height);
        System.out.println("");
    }

    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}