labuladong公众号笔记

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 14k | 阅读时长 ≈ 13 分钟

动态规划：不同的定义产生不同的解法

文章链接

键盘组合问题

收获

对状态机的定义不同，得到的状态转移方程就完全不同

经典面试题：最长回文子串（LeetCode第5题）

文章链接

经典面试题：最长回文子串

收获

回文子串有两个做法，一个是从中间展开的算法，一个是两侧向中间靠齐的dp

单调栈

文章链接

单调栈 Monotonic Stack 的使用

收获

  • 单调栈算法过程
    • 处理Next Greater Number，从后向前遍历
    • 先判断 栈是否为空 和 栈顶的值是不是比即将入栈的值小
    • 如果栈空，则说明找不到比该数大的数，将其Next Greater Number置为-1
    • 栈不为空，直到找到比该数大的数，将其置为栈顶，比其小的也就没有存在的意义了
    • 然后将该数的Next Greater Number定为栈顶元素，并将该数加入栈中
  • 处理循环数组
    • 将该数组的双倍长度构造出来，这样的话就就不仅能比较右边的数，还能比较左边的数了

二分查找算法详解

文章链接

二分查找算法详解

二分查找的框架

  • 最基本的框架1（形式是[a,b)）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int binarySearch(int nums[],int target){
        int left = 0;
        int right = nums.length;
        while(left < right){
            //防止计算mid时溢出
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid;
        }
        return -1;
    }

  • 最基本的框架2 (形式是[a,b])

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int binarySearch(int nums[],int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            //防止计算mid时溢出
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid - 1;
        }
        return -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
    /**
     * 返回的是比target小的数量，同时也是最左target的下标
     * @param nums
     * @param target
     * @return
     */
    int binarySearchLeft(int nums[],int target){
        int left = 0;
        int right = nums.length;
        while(left < right){
            //防止计算mid时溢出
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                right = mid;
            else if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid;
        }
        //要时刻注意处理边界，如果整个数组都没有这个target，则left会到nums.length
        // target 比所有数都大
        if (left == nums.length) return -1;
        // 类似之前算法的处理方式
        return nums[left] == target ? left : -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
    /**
     * 返回的是最右target的下标
     * @param nums
     * @param target
     * @return
     */
    int binarySearchRight(int nums[],int target){
        int left = 0;
        int right = nums.length;
        while(left < right){
            //防止计算mid时溢出
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                left = mid + 1;
            else if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid;
        }
        //要时刻注意处理边界，如果整个数组都没有这个target，则left会到nums.length
        // target 比所有数都大
        // return left - 1;
        if (left == 0) return -1;
        // 类似之前算法的处理方式
        return nums[left-1] == target ? (left-1) : -1;
    }

收获

  • 左侧边界的二分搜索，left即代表比target小的数的数量
  • 右侧边界的二分搜索，left即代表比target大的第一个数的下标，比如是5，则代表索引为4是target的最右侧数

最长递归子序列(LeetCode第300题)

文章链接

动态规划之最长递归子序列

两个方法：

  • dp
  • 扑克牌算法，运用二分查找

dp

注意事项

最重要的是先确定状态转移方程，并且明确dp数组的含义，这里要求的是最长递归子序列，所建立的dp数组是一个一维数组(为何选取的是一维数组呢？)，并且dp[i]的含义是指以索引i结尾的最长递归子序列。

采用归纳法可知，若dp[0…i-1]可知，则

1
2
3
4
for(int j = 0; j < i;j++){
	if(nums[j] < nums[i])
		dp[i] = Math.max(dp[i],dp[j]+1);
}

即dp[i]是之前的dp[0…i-1]，判断其是否小于nums[i]，若小于则nums[i]可以接到其后面，最后选取一个最长的递归子序列即可。

还有要考虑的就是base case，由于是最短递归子序列至少为1，所以base case为1，所以dp数组全部初始化为1即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lengthOfLtsByDp(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[j] < nums[i])
                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;
}

扑克牌算法

最长递归子序列其实类似于我们平时玩的蜘蛛纸牌，eg：2，3，1，9，7，4，6，3 ，同一堆的牌只能是小的放在大的上面，如上，就分成2，1 3 9，7，6，3 4 一共4堆，则最长递归子序列数为 4 。

至于如何处理扑克牌放置问题，则可以采用二分查找，因为堆顶都是有序的。

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
public int lengthOfLtsByBinarySearch(int[] nums){
    //堆的个数
    int piles = 0;
    //记录每个堆的最上面的牌，保证有序，所以必须利用最左侧边界的二分法
    int[] top = new int[nums.length];
    for(int i = 0;i < nums.length;i++){
        int poker = nums[i];
        int left = 0;
        int right = piles;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(poker < top[mid])
                right = mid;
            else if(poker > top[mid])
                left = mid + 1;
            else
                right = mid;
        }
        //left的取值有[0,nums.length],当left为nums.length时，这里是piles，说明牌堆上的第一张牌全部比它小，则说明此时需要新建一个牌堆
        if (left == piles)
            piles++;
        top[left] = poker;
    }
    return piles;
}

​

子序列解题模板

文章链接

子序列解题模板

收获

两种思路

  • dp数组为一维数组。常见题型有 最长递增子序列。在子数组array[0..i]中，以array[i]结尾的目标子序列（最长递增子序列）的长度是dp[i]。

    模板：

    1
    2
    3
    4
    5
    6
    7
    8
    int n = array.length;
    int[] dp = new int[n];

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = 最值(dp[i], dp[j] + ...)
        }
    }

  • dp数组为二维数组。二维数组又分为是对两字符串而言和一个字符串而言。

    模板：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int n = arr.length;
    int[][] dp = new dp[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (arr[i] == arr[j]) 
                dp[i][j] = dp[i][j] + ...
            else
                dp[i][j] = 最值(...)
        }
    }
    • 对一个字符串使用的dp为二维数组。常见题型有之前做过的 最长回文子串，使用双指针，从两边向中间靠拢，二维分别指的是左侧指针和右侧指针的索引值。可以推广到最长回文子序列。
    • 对两个字符串使用的dp为二维数组。例如 编辑距离 和 最长公共子序列

回文子序列的求解(LeetCode第516题)

回文子序列的求解，是在回文子串的基础上进行的，dp[i][j] 的长度取决于s[i]和s[j]以及dp[i+1][j-1]

  • 当s[i] == s[j]时，dp[i][j] = dp[i+1][j-1] + 2
  • 当s[i] != s[j]时， dp[i][j] = Math.max(dp[i][j-1]，dp[i+1][j])

当转移方程写好后，最大的难点就是如何遍历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
/**
     * 斜着遍历的dp
     * @param nums
     * @return
     */
    private static int dp(int[] nums){
        int[][] dp = new int[nums.length][nums.length];
//        Arrays.fill(dp, 0);
        int j = 0;
        for(int i = 0;i < nums.length;i++){
            dp[i][i] = 1;
        }
        //斜着循环遍历
        for(int n = 1;n < nums.length;n++){
            for(int i = 0; i < nums.length - n;i++){
                j = i + n;
                if(nums[i] == nums[j])
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
            }
        }
        return dp[0][nums.length-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
    /**
     * 逆循环遍历的dp
     * @param nums
     * @return
     */
    private  static int dpByInverse(int[] nums){
        int[][] dp = new int[nums.length][nums.length];
//        Arrays.fill(dp, 0);
//        int j = 0;
        int n = nums.length;
        for(int i = 0;i < nums.length;i++){
            dp[i][i] = 1;
        }
        // 反着遍历保证正确的状态转移
        for (int i =  n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // 状态转移方程
                if (nums[i] == nums[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][nums.length-1];
    }

编辑距离（LeetCode第72题）

先总结一哈：从后往前，然后写递归函数，然后画DP Table，写非递归，注意Base case！

文章链接

编辑距离

题目

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符
示例 1:

1
2
3
4
5
6
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

1
2
3
4
5
6
7
8
输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

思路

个人觉得公众号说的有的啰嗦哈~ 我就稍微总结一下我的想法：

  • 拿到题目，又是两个字符串之间的问题，毫无疑问第一想法想到使用双指针的dp，因为一般遇到两个字符串的问题都是采用dp二维数组解决(双指针)；
  • dp解决问题，首先就要搞清楚dp数组代表什么，其次就是状态转移有哪几种情况！
  • 一般dp二维数组 dp[i][j] ,代表以s1[i-1]、s2[j-1]结尾的转换的最少操作数，为啥是i-1,j-1！因为dp是从dp[1][1]开始的，代表字符串的第一个字符！！
  • 搞明白了dp数组是啥含义，现在就要搞清楚有哪几种状态转移，从公众号中可以看到，dp[i][j]想要往前移动，则可以进行删除、修改、插入操作，如果双指针指向的字符相同，则无需进行任何操作，直接向前移动就行，也就是此时 dp[i][j] = dp[i-1][j-1] ;
  • 剩下的插入、删除、修改如何做呢…取三者最小值就好了嘛！！！
  • 其实这个画个DP表就非常的清晰了，画DP表也能提醒我们注意Base Case,因为没有Base Case ，我们是肯定写不出来DP表中的值的；
  • 有个注意的点，就是备忘录做法是从0开始的，所以当i或者j = -1时，此时的i、j代表的是数组的下标，是从0开始的，比如说此时j = 5的，说明还有6个字符需要删除，所以要记得+1 ，而dp是从dp[1][1]开始的(比如两个字符串’’abc””acd”，dp[1][1]指的是都指向a)！！！！这个很容易错！

三种做法

  • 常规暴力递归(超时)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minDistance(String word1, String word2) {
     int len = dp_violence(word1,word2,word1.length()-1,word2.length()-1);
        return len;
    }

    private int dp_violence(String s1,String s2,int i, int j) {
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;
        if(s1.charAt(i) == s2.charAt(j)){
            return dp_violence(s1,s2,i-1,j-1);
        }
        else{
             int min = Math.min(dp_violence(s1,s2,i-1,j-1)+1,
                    dp_violence(s1,s2,i-1,j)+1);
             min = Math.min( dp_violence(s1,s2,i,j-1)+1,min);
             return min;
        }

    }
}
  • 带备忘录的递归(这个貌似比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
class Solution {
    public int minDistance(String word1, String word2) {
            int[][] beiwanglu = new int[word1.length()][word2.length()];
        int len = dp_beiwanglu(beiwanglu,word1,word2,word1.length()-1,word2.length()-1);
        return len;
    }

    private int dp_beiwanglu(int[][] beiwanglu,String s1, String s2, int i, int j) {

        if(i == -1) return j + 1;

        if(j == -1) return i + 1;

        if(beiwanglu[i][j] != 0){
            return beiwanglu[i][j];
        }
        if(s1.charAt(i) == s2.charAt(j)){
            beiwanglu[i][j] = dp_beiwanglu(beiwanglu,s1,s2,i-1,j-1);
            return dp_beiwanglu(beiwanglu,s1,s2,i-1,j-1);
        }
        else{
            int min = Math.min(dp_beiwanglu(beiwanglu,s1,s2,i-1,j-1)+1,
                    dp_beiwanglu(beiwanglu,s1,s2,i-1,j)+1);
            min = Math.min( dp_beiwanglu(beiwanglu,s1,s2,i,j-1)+1,min);
            beiwanglu[i][j] = min;
            return min;
        }
    }
}
  • dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minDistance(String s1, String s2) {
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        for(int i = 0;i<= s1.length();i++){
            dp[i][0] = i;
        }
        for(int j = 0;j<=s2.length();j++){
            dp[0][j] = j;
        }
        for(int i = 1;i<= s1.length();i++){
            for(int j = 1;j <= s2.length();j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j-1] + 1,dp[i-1][j] + 1);
                    dp[i][j] = Math.min(dp[i][j],dp[i][j-1] + 1);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}

最长公共子序列问题（LeetCode第1143题）

典型的dp二维数组解决，太简单了…

  • 第一个要注意的就是该dp可以优化，当双指针指向的字符不等时，dp[i-1][j-1]可以不用考虑！！！！因为max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])是一定轮不到最后这个的；
  • 第二个要注意的点就是记得Base Case,记得要画DP表！
  • 同样要注意这里的第一个字符串对应的就是dp[1][1]！！！！！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for(int i = 1;i <= text1.length();i++){
            for(int j = 1;j <=text2.length();j++){
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        return dp[text1.length()][text2.length()];
    }
}

滑动窗口算法(示例:LeetCode第1143：最小覆盖子串问题)

  • Tip：最重要的是过最后一个用例的艰辛，因为需要考虑到Integer是一个对象，超过-127~128之后会new一个新的对象，导致就算是值相等，其也会显示不相等！！！！！！！

文章链接

滑动窗口算法

代码

文章中使用C++实现的，我是在LeetCode用的Java实现的

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
class Solution {
    public String minWindow(String s, String t) {
         // 利用双指针的思想，先记录下t会出现的单词以及次数
        // 然后右指针开始遍历，每当一个单词及其次数到位后，当前单词就匹配完成，直到所有单词都匹配完成
        // 然后记录下当前的子串的开始和结尾，即左右指针的位置
        // 然后开始试图移动左指针，当然前提是t中所有字符然后全部匹配完成，否则就跳出循环，继续走右边指针
        // 直到右边指针走到底，如果走到底长度依旧没有，则说明找不到最小子串，返回"" 否则返回适当的子串
        int left = 0,right = 0;
        //计算匹配的单词数量
        int match = 0;
        //统计目标字符串的不同字符的个数
        int nums = 0;
        int min_length = Integer.MAX_VALUE;
        int start = 0;
        char[] t_char = t.toCharArray();
        char[] s_char = s.toCharArray();
        HashMap<Character, Integer> windows = new HashMap<Character, Integer>();
        HashMap<Character,Integer> tt = new HashMap<Character, Integer>();
        // 用两个map来存储两个字符串，存储方式为key为单词，value为单词出现的数量
        //
        for (char t1: t_char){
            if(tt.containsKey(t1)) {
                int value = tt.get(t1).intValue();
                tt.put(t1, ++value);
            }
            else{
                nums++;
                tt.put(t1,1);
            }
        }

        while(right < s.length()){
            if(windows.containsKey(s_char[right])){
                int windows_value = windows.get(s_char[right]).intValue();
                windows.put(s_char[right],++windows_value);
            }
            else{
                windows.put(s_char[right],1);
            }
            //如果全部符合要求
            if(tt.containsKey(s_char[right]) && windows.get(s_char[right]).intValue() == tt.get(s_char[right]).intValue()){
                    match++;
            }
            right++;
            while(match == nums){
                //说明已经找到一个符合条件的了，记录下该字符串的起始和结束位置
                int Len = right - left;
                if(Len < min_length)
                {
                    min_length = Math.min(min_length,Len);
                    start = left;
                }
                int left_value = windows.get(s_char[left]).intValue();
                left_value--;
                windows.put(s_char[left],left_value);
                if(tt.containsKey(s_char[left]) && windows.get(s_char[left]).intValue() < tt.get(s_char[left]).intValue()){
                    match--;
                }
                left++;

            }

        }
        return min_length == Integer.MAX_VALUE ? "" : s.substring(start,min_length +start);
    }
}

最大子序列和(LeetCode第53题)

先总结一下，可以运用 dp 和 滑动窗口 两种方法！！！

题目

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

示例:

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

思路

  • dp

    • 要的是子串，必然可以用dp，而且是单子串且非回文，则必然使用一维dp数组
    • 只要定义好了dp数组，这道题就没有任何难度，dp[i]定义为以i为索引的字符结尾的最大和
    • 则dp[i] = Math.max(dp[i-1],nums[i])，然后取dp[i]中最大的即可！
    • 这题只有一个小难点，那就是找Base Case,好像并不存在Base Case,但是我们可以创造Base Case,可以令dp[0] = nums[0]，这样就有Base Case了，同时注意哈，这里不需要将dp数组的大小变为nums.length+1,因为这个题目不存在Base Case,所以dp只会产生n个数，不需要n+1个存储空间，像上文的dp二维数组，就存在BaseCase，当有一个为0时，有相应的取值！总而言之，一定要特别注意dp的数组大小以及BaseCase。

  • 滑动窗口

    比较简单的思路。就是sum如果大于0了，就移动右指针就行，如果是小于0了，就比较sum和num[i]，取最大值(相当于移动左指针)，直到循环结束。

代码

  • dp
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
         //res[i] = Math.max(res[i-1] + nums[i],nums[i])
        int[] res = new int[nums.length];
        res[0] = nums[0];
        int max = res[0];
        for(int i = 1;i < nums.length;i++){
            res[i] = Math.max(res[i-1] + nums[i],nums[i]);
            max = Math.max(res[i],max);
        }
        return  max;
    }
}
  • 滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for(int num:nums){
            if(sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(sum,res);
        }
        return res;
    }
}

打家劫舍 I、II、III (LeetCode第198、213、337)

文章链接

打家劫舍系列

I 的代码

  • 自己写的(感觉写的有点啰嗦~)
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
class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 0;
        if(nums.length == 0 ){
            return 0;
        }
        if(nums.length == 1){
            dp[0] = nums[0];
            res = dp[0];
            return res;
        }
       if(nums.length == 2){
           dp[1] = Math.max(nums[1],nums[0]);
           res = dp[1];
           return res;

       }
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],nums[0]);
        for(int i = 2;i < nums.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
      	res = Math.max(dp[nums.length-1],res)
        return res;
    }
}
  • 高分题解
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n == 0 ? 0 : nums[0];
        int[] memo = new int[n];
        memo[0] = nums[0];
        memo[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++)
            memo[i] = Math.max(memo[i - 1], nums[i] + memo[i - 2]);
        return memo[n - 1];
    }
}

II 的代码

分两次dp就好了，一次[0,nums.length-2]，一次[1,nums.length-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
class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 0;
        if(nums.length == 0 ){
            return 0;
        }
        if(nums.length == 1){
            dp[0] = nums[0];
            res = dp[0];
            return res;
        }
       if(nums.length == 2){
           dp[1] = Math.max(nums[1],nums[0]);
           res = dp[1];
           return res;
       }
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],nums[0]);
        for(int i = 2;i < nums.length-1;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        dp[1] = nums[1];
        dp[2] = Math.max(nums[1],nums[2]);
        for(int i = 3;i < nums.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        res = Math.max(dp[nums.length-1],dp[nums.length-2]);
        return res;
    }
}

III 的代码

这是一个树形的dp问题，解决方法是采用一个一维数组，之前的I II只用到了dp[nums.length-1]，这里用到了两个,而且这里的dp竟然用了递归哟…

Tip:特殊做法记忆记忆记忆！！！

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
     int[] res = robIn(root);
        return Math.max(res[0],res[1]);
        
    }
    private static int[] robIn(TreeNode root){
        //用一个数组记录偷根节点和不偷根节点两种情况，这里很特殊用了dp同时还搭配了递归
      	//这就是自底向上的递归，详情可以见LeetCode递归专题
        int[] res = new int[2];
        if(root == null){
            return res;
        }
        int[] left = robIn(root.left);
        int[] right = robIn(root.right);
        //偷根节点
        res[0] = root.val + left[1] + right[1];
      	//不偷根节点
        res[1] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        return res;
    }
}
Thank you for your accept. mua！
-------------本文结束感谢您的阅读-------------