动态规划练习题——LeetCode

  将原问题拆解成若干个子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

  最优子结构：通过求子问题的最优解，可以获得原问题的最优解。且有重叠子结构，才能用记忆化搜索和动态规划

第一二节，动态规划

70. 爬楼梯（简单）

自己的想法

方法一：递归（自上而下的解决问题）

  超时，也可以使用记忆化搜索解决。

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

方法二：动态规划（自下而上）

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.1 MB, 在所有 Java 提交中击败了82.77%的用户

class Solution {
    public int climbStairs(int n) {
        int a = 0;
        int b = 1;
        int c = 0;
        while (n-- != 0) {
            c = a + b;
            a = b;
            b = c; 
        }
        return b;
    }
}

120. 三角形最小路径和（中等）

看题解后

方法一：动态规划（从上向下）

  使用 dp 数组记录从 dp[0][0] 走到 dp[i][j] 所需的最小值。

• 执行用时：3 ms, 在所有 Java 提交中击败了75.08%的用户
• 内存消耗：38.7 MB, 在所有 Java 提交中击败了22.26%的用户

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 获取三角形高度
        int length = triangle.size();
        // 够建记忆数组，记录从 dp[0][0] 走到 dp[i][j] 所需的最小值
        int[][] dp = new int[length][length];
        // 初始化顶部
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < length; i++) {
            // 为了防止越界，第一个特殊处理
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                // 当前值 + （dp[i - 1][j]、dp[i - 1][j - 1] 的最小值）求出到 dp[i][j] 所需的最小值
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
            }
            // 最后一个特殊处理，因为 dp[i - 1][j] 为 0
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        // 求出到底部的最短路径
        int min = dp[length - 1][0];
        for (int i = 1; i < length; ++i) {
            min = Math.min(min, dp[length - 1][i]);
        }
        return min;
    }
}

方法二：空间优化

  将方法一的二维数组，优化为一维数组，每次循环进行覆盖之前的值。

• 执行用时：2 ms, 在所有 Java 提交中击败了94.40%的用户
• 内存消耗：38.8 MB, 在所有 Java 提交中击败了6.42%的用户

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 获取三角形高度
        int length = triangle.size();
        int[] dp = new int[length];
        // 初始化顶部
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < length; i++) {
            // 最后一个特殊处理，因为 dp[i] 为 0
            dp[i] = dp[i - 1] + triangle.get(i).get(i);
            for (int j = i - 1; j > 0; j--) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j - 1]);
            }
            // 为了防止越界，第一个特殊处理
            dp[0] += triangle.get(i).get(0);
        }
        // 求出到底部的最短路径
        int min = dp[0];
        for (int i = 1; i < length; ++i) {
            min = Math.min(min, dp[i]);
        }
        return min;
    }
}

方法三：原地修改

  不适用额外数组，在集合上进行操作

• 执行用时：7 ms, 在所有 Java 提交中击败了12.29%的用户
• 内存消耗：38.9 MB, 在所有 Java 提交中击败了5.18%的用户

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 获取三角形高度
        int length = triangle.size();
        // 初始化顶部
        for (int i = 1; i < length; i++) {
            // 为了防止越界，第一个特殊处理
            triangle.get(i).set(0, triangle.get(i - 1).get(0) + triangle.get(i).get(0));
            for (int j = 1; j < i; j++) {
                // 当前值 + （triangle[i - 1][j]、triangle[i - 1][j - 1] 的最小值）求出到 triangle[i][j] 所需的最小值
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i - 1).get(j), triangle.get(i - 1).get(j - 1)));
            }
            // 最后一个特殊处理，因为 triangle[i - 1][j] 为 0
            triangle.get(i).set(i, triangle.get(i - 1).get(i - 1) + triangle.get(i).get(i));
        }
        // 求出到底部的最短路径
        int min = triangle.get(length - 1).get(0);
        for (int i = 1; i < length; ++i) {
            min = Math.min(min, triangle.get(length - 1).get(i));
        }
        return min;
    }
}

方法四：动态规划（从下往上）

• 执行用时：2 ms, 在所有 Java 提交中击败了94.40%的用户
• 内存消耗：38.7 MB, 在所有 Java 提交中击败了12.76%的用户

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 获取三角形高度
        int length = triangle.size();
        int[] dp = new int[length + 1];
        // 从下往上遍历
        for (int i = length - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
}

64. 最小路径和（中等）

自己的想法

方法一：动态规划

• 执行用时：3 ms, 在所有 Java 提交中击败了87.31%的用户
• 内存消耗：41.4 MB, 在所有 Java 提交中击败了9.17%的用户

class Solution {
    public int minPathSum(int[][] grid) {
        // 初始化行
        for (int i = 1; i < grid[0].length; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        // 初始化列
        for (int i = 1; i < grid.length; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

看题解后

方法二：动态规划

  不修改原数组，使用一维数组记录路径值。

• 执行用时：2 ms, 在所有 Java 提交中击败了97.98%的用户
• 内存消耗：41.3 MB, 在所有 Java 提交中击败了31.21%的用户

class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid[0].length;
        int[] state = new int[n];
        state[0] = grid[0][0];
        // 给第一行初始化
        for (int i = 1; i < n; i++) {
            state[i] = grid[0][i] + state[i - 1];
        }
        for (int i = 1; i < grid.length; i++) {
            int j = 0;
            // 计算到达 grid[i][j] 的最小路径
            state[j] = state[j] + grid[i][j];
            for (j = 1; j < n; j++) {
                // state[j - 1] 存储的是到达 grid[i][j - 1] 的最小路径。
                // state[j] 存储的是到达 grid[i - 1][j] 的最小路径。
                state[j] = Math.min(state[j - 1], state[j]) + grid[i][j];
            }
        }
        return state[n - 1];
    }
}

第三节，发现重叠子问题

343. 整数拆分（中等）

自己的想法

  这个题和切绳子一样。

方法一：递归（超时）

  n 可以拆分为 (1, n - 1)、(2, n - 2)、(3, n - 3) ... (i, n - i)，对于 (n - i) 可以拆分也可以不拆分。

class Solution {

    public int integerBreak(int n) {
        if (n == 1) {
            return 1;
        }
        int max = 0;
        for (int i = 1; i <= n / 2; i++) {
            // 不拆分
            max = Math.max(max, i * (n - i));
            // 拆分
            max = Math.max(max, i * integerBreak(n - i));
        }
        return max;
    }
}

方法二：记忆化搜索

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.2 MB, 在所有 Java 提交中击败了62.33%的用户

class Solution {

    int[] dp;

    public int integerBreak(int n) {
        dp = new int[n + 1];
        return dp(n);
    }

    public int dp(int n) {
        if (n == 1) {
            return 1;
        }
        if (dp[n] != 0) {
            return dp[n];
        }
        int max = 0;
        for (int i = 1; i <= n / 2; i++) {
            max = Math.max(max, i * (n - i));
            max = Math.max(max, i * dp(n - i));
        }
        dp[n] = max;
        return max;
    }
}

方法三：动态规划

  对于 n 可以拆分为：1*dp[n-1]，2*dp[n-2]，3*dp[n-3]...也可以不对 n-1，n-2...进行拆分，所以对于 n 有两种情况：i*(n-i) 和 i*dp[n-i]。

• 执行用时：1 ms, 在所有 Java 提交中击败了65.26%的用户
• 内存消耗：34.9 MB, 在所有 Java 提交中击败了93.84%的用户

class Solution {
    public int integerBreak(int n) {
        // 长度为n的最佳的拆分方案
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], j * (i - j));
                dp[i] = Math.max(dp[i], j * dp[i - j]);
            }
        }
        return dp[n];
    }
}

代码优化：二层循环可以优化为

for (int j = 1; j < i / 2 + 1; j++)
或
for (int j = 1; j <= i / 2; j++) 

方法四：贪心

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.2 MB, 在所有 Java 提交中击败了43.04%的用户

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return (n - 1) * 1;
        }
        int result = 1;
        if (n % 3 == 1) {
            result *= 4;
            n -= 4;
        } else if (n % 3 == 2) {
            result *= 2;
            n -= 2;
        }
        return (int)(result * Math.pow(3, n / 3));
    }
}

279. 完全平方数（中等）

看题解后

方法一：递归（超时）

  对于每个数都进行拆分，只要 n - i * i大于 0（i>0），则向下递归。

class Solution {
    public int numSquares(int n) {
        // 默认全部拆分为 1
        int min = n;
        // 开始分割
        for (int i = 1; n - i * i >= 0; i++) {
            // 将其进行分割
            min = Math.min(min, numSquares(n - i * i) + 1);
        }  
        return min;
    }
}

方法二：记忆化搜索

• 执行用时：86 ms, 在所有 Java 提交中击败了20.12%的用户
• 内存消耗：38.6 MB, 在所有 Java 提交中击败了10.46%的用户

class Solution {

    int[] dp;

    public int numSquares(int n) {
        dp = new int[n + 1];
        return dp(n);
    }

    public int dp(int n) {
        // 默认全部拆分为 1
        int min = n;
        if (dp[n] != 0) {
            return dp[n];
        }
        // 开始分割
        for (int i = 1; n - i * i >= 0; i++) {
            // 将其进行分割
            min = Math.min(min, dp(n - i * i) + 1);
        }  
        dp[n] = min;
        return min;
    }
}

方法三：动态规划

• 执行用时：41 ms, 在所有 Java 提交中击败了76.57%的用户
• 内存消耗：37.3 MB, 在所有 Java 提交中击败了90.60%的用户

class Solution {

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; i - j * j >= 0; j++) {
                // 将其进行分割
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
             }
         }
        return dp[n];
    }
}

方法四：贪心和数学（不会）

91. 解码方法

自己的想法

方法一：记忆化搜索（从后往前）

  递归（超时），改为记忆化搜索。

• 执行用时：125 ms, 在所有 Java 提交中击败了9.46%的用户
• 内存消耗：36.7 MB, 在所有 Java 提交中击败了51.85%的用户

class Solution {

    int[] str;
    int[] dp;

    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        str = new int[n];
        dp = new int[n];
        // 转为数字数组
        for (int i = 0; i < n; i++) {
            str[i] = s.charAt(i) - '0';
        }
        return dp(n - 1);
    }

    public int dp(int i) {
        // 遍历完，则返回
        if (i == -1) {
            return 1;
        }
        if (dp[i] != 0) {
            return dp[i];
        }
        int value = 0;
        // 当前值不为0，则可以拆分
        if (str[i] != 0) {
            value += dp(i - 1);
        }
        // 前一个值不为0且组合起来<=26，则可以拆分
        if (i > 0 && str[i - 1] != 0 && (str[i - 1] * 10 + str[i] <= 26)) {
            value += dp(i - 2);
        }
        dp[i] = value;
        return value;
    }
}

方法二：记忆化搜索（从前往后）

• 执行用时：13 ms, 在所有 Java 提交中击败了9.46%的用户
• 内存消耗：36.5 MB, 在所有 Java 提交中击败了91.52%的用户

class Solution {

    int[] str;
    int[] dp;
    int n;

    public int numDecodings(String s) {
        n = s.length();
        if (n == 0) {
            return 0;
        }
        str = new int[n];
        dp = new int[n];
        // 转为数字数组
        for (int i = 0; i < n; i++) {
            str[i] = s.charAt(i) - '0';
        }
        return dp(0);
    }

    public int dp(int i) {
        // 遍历完，则返回
        if (i == n) {
            return 1;
        }
        if (dp[i] != 0) {
            return dp[i];
        }
        int value = 0;
        // 当前值不为0，则可以拆分
        if (str[i] != 0) {
            value += dp(i + 1);
        }
        // 当前值不为0且组合起来<=26，则可以拆分
        if (i < n - 1 && str[i] != 0 && (str[i] * 10 + str[i + 1] <= 26)) {
            value += dp(i + 2);
        }
        dp[i] = value;
        return value;
    }
}

方法三：动态规划（从前往后）

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.7 MB, 在所有 Java 提交中击败了41.35%的用户

class Solution {

    public int numDecodings(String s) {
        int n = s.length();
        int[] str = new int[n + 1];
        int[] dp = new int[n + 1];
        // 转为数字数组
        for (int i = 1; i <= n; i++) {
            str[i] = s.charAt(i - 1) - '0';
        }
        // 类似于记忆化搜索的 -1
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (str[i] != 0) {
                dp[i] += dp[i - 1];
            }
            // 判断等不能向前进行两组合
            if (i > 1 && str[i - 1] != 0 && (str[i - 1] * 10 + str[i] <= 26)) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

方法四：动态规划（从后往前）

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.8 MB, 在所有 Java 提交中击败了27.58%的用户

class Solution {

    public int numDecodings(String s) {
        int n = s.length();
        int[] str = new int[n + 1];
        int[] dp = new int[n + 1];
        // 转为数字数组
        for (int i = 0; i < n; i++) {
            str[i] = s.charAt(i) - '0';
        }
        // 类似于记忆化搜索的 n
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (str[i] != 0) {
                dp[i] += dp[i + 1];
            }
            // 判断等不能向后进行两组合
            if (i < n - 1 && str[i] != 0 && (str[i] * 10 + str[i + 1] <= 26)) {
                dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }
}

方法五：动态规划（从前往后，空间压缩）

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.7 MB, 在所有 Java 提交中击败了38.01%的用户

class Solution {

    public int numDecodings(String s) {
        int n = s.length();
        int[] str = new int[n + 1];
        // 转为数字数组
        for (int i = 1; i <= n; i++) {
            str[i] = s.charAt(i - 1) - '0';
        }
        // 只记录中间变量，节约空间
        int a = 1, b = 1, c = 0;
        for (int i = 1; i <= n; i++) {
            // 每次初始化 c
            c = 0;
            if (str[i] != 0) {
                c += b;
            }
            // 判断等不能向前进行两组合
            if (i > 1 && str[i - 1] != 0 && (str[i - 1] * 10 + str[i] <= 26)) {
                c += a;
            }
            a = b;
            b = c;
        }
        return c;
    }
}

62. 不同路径

自己的想法

方法一：记忆化搜索

  递归（超时）。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35 MB, 在所有 Java 提交中击败了86.47%的用户

class Solution {

    int[][] dp;
    int m, n;

    // 使用递归
    public int uniquePaths(int m, int n) {
        this.m = m;
        this.n = n;
        dp = new int[m][n];
        return dp(m - 1, n - 1);
    }

    public int dp(int i, int j) {
        // 越界则结束
        if (i < 0 || i == m || j < 0 || j == n) {
            return 0;
        }
        // 到终点
        if (i == 0 && j == 0) {
            return 1;
        }
        // 如果不为 0，则该节点走过
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int tmp = dp(i - 1, j) + dp(i, j - 1);
        dp[i][j] = tmp;
        return tmp;
    }
}

方法二：动态规划

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.1 MB, 在所有 Java 提交中击败了72.66%的用户

class Solution {

    // 使用递归
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // 行列初始化
        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];
    }
}

方法三：空间压缩

  使用一维的 dp 数组存储当前行的所有点的路径数，然后遍历每一行。dp[j - 1] 存储的是到达 dp[i][j - 1] 的最小路径，dp[j] 存储的是到达 dp[i - 1][j] 的最小路径。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35 MB, 在所有 Java 提交中击败了86.86%的用户

class Solution {

    // 使用递归
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        // 行列初始化
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // dp[j - 1] 存储的是到达 dp[i][j - 1] 的最小路径。
                // dp[j] 存储的是到达 dp[i - 1][j] 的最小路径。
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

63. 不同路径 II

自己的想法

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：37.8 MB, 在所有 Java 提交中击败了46.23%的用户

方法一：动态规划

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        // 使用一维数组记录当前行的每格的路径数
        int[] dp = new int[m];
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        // 遍历每一行
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果当前不是障碍物，则进行累加
                if (obstacleGrid[i][j] != 1) {
                    if (j != 0) {
                        dp[j] += dp[j - 1];
                    }
                } else {
                    // 是障碍物，则路径为0
                    dp[j] = 0;
                }
            }
        }
        return dp[m - 1];
    }
}

第四节，状态的定义和状态转移

198. 打家劫舍

自己的想法

方法一：递归（超时）

class Solution {
    public int rob(int[] nums) {
        return dfs(nums, 0, true, 0);
    }

    public int dfs (int[] nums, int index, boolean is, int sum) {
        // 到结尾则返回
        if (index == nums.length) {
            return sum;
        }
        // 不选的情况
        int value = dfs( nums, index + 1, true, sum);
        // 前一个没选，当前可以选
        if (is) {
            value = Math.max(value, dfs(nums, index + 1, false, sum + nums[index]));
        }
        return value;
    }
}

方法二：动态规划

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.8 MB, 在所有 Java 提交中击败了57.87%的用户

class Solution {

    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            // 选和不选两种情况
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }
        return dp[nums.length];
    }
}

看题解后

方法三：递归（超时）

class Solution {

    public int rob(int[] nums) {
        return dfs(nums, 0);
    }

    public int dfs(int[] nums, int index) {
        if (index >= nums.length) {
            return 0;
        }
        int sum = 0;
        for (int i = index; i < nums.length; i++) {
            sum = Math.max(sum, nums[i] + dfs(nums, i + 2));
        }
        return sum;
    }
}

方法四：记忆化搜索（超时）

class Solution {

    int[] dp;

    public int rob(int[] nums) {
        dp = new int[nums.length];
        return dfs(nums, 0);
    }

    public int dfs(int[] nums, int index) {
        if (index >= nums.length) {
            return 0;
        }
        if (dp[index] != 0) {
            return dp[index];
        }
        int sum = 0;
        for (int i = index; i < nums.length; i++) {
            sum = Math.max(sum, nums[i] + dfs(nums, i + 2));
        }
        dp[index] = sum;
        return sum;
    }
}

方法五：动态规划

• 执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.8 MB, 在所有 Java 提交中击败了46.99%的用户

class Solution {

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        // 偷最后一个
        dp[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i] = Math.max(dp[i], nums[j] + (j + 2 < n ? dp[j + 2] : 0));
            }
        }
        return dp[0];
    }
}

213. 打家劫舍 II

动态规划

class Solution {

    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, length - 1), robRange(nums, 1, length));
    }

    public int robRange(int[] nums, int start, int end) {
        int[] dp = new int[end + 1];
        dp[start + 1] = nums[start];
        for (int i = 2; i <= end; i++) {
            // 选和不选两种情况
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }
        return dp[end];
    }
}

2、最大子序和（简单）

自己的想法

方法一：动态规划

  对于序列中的每一个数都有选与不选两种情况。因为要求序列是连续的子数组，所有如果选，值是最大子序列和+当前数；如果不选，值是当前数。我们只需要记录当前序列的最大值，就可以推出后面序列的最大值。

• 执行用时：1 ms, 在所有 Java 提交中击败了94.73%的用户
• 内存消耗：38.4 MB, 在所有 Java 提交中击败了46.62%的用户

class Solution {
    public int maxSubArray(int[] nums) {
        // 记录当前子序列和的最大值
        int take = 0;
        int result = Integer.MIN_VALUE;
        for (int num : nums) {
            // 求出对于当前数，选与不选，哪个价值最高
            take = Math.max(take + num, num);
            // 记录最大的值
            result = Math.max(take, result);
        }
        return result;
    }
}

3、最长递增子序列（中等）

看题解后

方法一：动态规划

  使用数组记录以当前下标值结尾的最长递增子序列的长度（初始化为 1）。

• 执行用时：74 ms, 在所有 Java 提交中击败了47.45%的用户
• 内存消耗：38 MB, 在所有 Java 提交中击败了79.39%的用户

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 记录以当前下标值结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            // 初始化
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                // 判断当前值，是否可以继续延伸之前的序列
                if (nums[i] > nums[j]) {
                    // 如果可以延伸，求最佳
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

方法二：贪心 + 二分查找

  上升子序列的结尾的数越小，那么遍历的时候后面接上一个数，会有更大的可能构成一个长度更长的上升子序列。既然结尾越小越好，我们可以记录在长度固定的情况下，结尾最小的那个元素的数值。

  用 tail[i] 表示：长度为 i 的所有上升子序列的结尾的最小值。tail[1] 表示长度为 1 的所有上升子序列中，结尾最小的元素的数值。

• 执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：37.8 MB, 在所有 Java 提交中击败了95.81%的用户

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 记录指定长度结尾的最小数，下标代表长度，值代表最小的数
        int[] tail = new int[nums.length + 1];
        tail[1] = nums[0];
        // 记录 tail 有效元素的下标，即递增子序列的最大长度
        int index = 1;
        // 遍历数组
        for (int i = 1; i < nums.length; i++) {
            // 如果当前数，大于序列的最后元素，则向后追加。表示序列可以变长
            if (nums[i] > tail[index]) {
                tail[++index] = nums[i];
            } else {
                // 如果序列不能改变，则更新数组的值
                // 因为只有子序列的结尾的数越小，那么遍历的时候后面接上一个数，会有更大的可能构成一个长度更长的上升子序列
                // 使用二分查找，查找 tail 数组中第一个大于等于 nums[i] 的数进行替换
                int left = 1, right = index;
                while (left < right) {
                    int mid = (left + right) >> 1;
                    if (tail[mid] < nums[i]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                tail[left] = nums[i];
            }
        }
        return index;
    }
}

6、打家劫舍（中等）

自己的想法

方法一：动态规划

  创建 dp 数组，记录对于当前房间，偷与不偷的最大价值。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.7 MB, 在所有 Java 提交中击败了81.95%的用户

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        // 0 代表偷了，1 代表没偷
        int[][] dp = new int[n][2];
        dp[0][0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = nums[i] + dp[i - 1][1];
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}

看题解后

方法二：动态规划（优化空间）

  创建 dp 数组，记录对于当前房间，偷或不偷的最大价值。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.4 MB, 在所有 Java 提交中击败了98.99%的用户

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            // 计算偷与不偷哪个价值大
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
}

方法三：动态规划 + 滚动数组（优化空间）

  省去 dp 数组，使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。使用两个中间变量记录值。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.6 MB, 在所有 Java 提交中击败了89.89%的用户

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int tmp = second;
            // 计算偷与不偷哪个价值大
            second = Math.max(first + nums[i], second);
            first = tmp;
        }
        return second;
    }
}