LeeCode三百题-动态规划

发表于 2021-04-23 更新于 2026-06-20 分类于 LeeCode三百题

[TOC]

代码工程获取

git clone --depth=1 https://gitee.com/SevDaisy/LeeCode300.git

#198 打家劫舍

动态规划题
2021-4-23
- 答案看懂了，但是让我自己写八成不出来。
- 动态规划做的不够多。

package Order300;

public class T198_house_robber {

  static class Solution {

    public int rob(int[] nums) {
      /* 鲁棒性 特殊条件 输入为空 */
      if (nums == null || nums.length == 0) {
        return 0;
      }
      int iMax = nums.length;
      /* 鲁棒性 特殊条件 仅有一间房 */
      if (iMax == 1) {
        return nums[0];
      }

      int[] dp = new int[iMax];
      /* dp起点 */
      dp[0] = nums[0];
      dp[1] = Math.max(nums[0], nums[1]);
      for (int i = 2; i < iMax; i++) {
        /* dp递推式 */
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
      }
      return dp[iMax - 1];
    }
  }
}

修改原题左右各两家

原题是：会提醒左右各一家报警
如果改成：会提醒左右各两家报警
则，算法变更如下

package Order300;

public class T198_house_robber {

  static class Solution {

    public int rob(int[] nums) {
      /* 鲁棒性 特殊条件 输入为空 */
      if (nums == null || nums.length == 0) {
        return 0;
      }
      int iMax = nums.length;
      /* 鲁棒性 特殊条件 仅有一间房 */
      if (iMax == 1) {
        return nums[0];
      }

      int[] dp = new int[iMax];
      /* dp起点 */
      dp[0] = nums[0];
      dp[1] = Math.max(nums[0], nums[1]);
      for (int i = 2; i < iMax; i++) {
        /* dp递推式 */
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
      }
      return dp[iMax - 1];
    }
  }

  /**
   * 原题是：会提醒左右各一家报警
   * 如果改成：会提醒左右各两家报警
   * 则，算法变更如下
   */
  static class Solution_2 {

    public int rob(int[] nums) {
      /* 鲁棒性 特殊条件 输入为空 */
      if (nums == null || nums.length == 0) {
        return 0;
      }
      int iMax = nums.length;
      /* 鲁棒性 特殊条件 仅有一间房 */
      if (iMax == 1) {
        return nums[0];
      }
      /* 鲁棒性 特殊条件 仅有两间房 */
      if (iMax == 2) {
        return Math.max(nums[0], nums[1]);
      }

      int[] dp = new int[iMax];
      /* dp起点 */
      dp[0] = nums[0];
      dp[1] = Math.max(nums[0], nums[1]);
      dp[2] = Math.max(dp[1], nums[2]);
      for (int i = 3; i < iMax; i++) {
        /* dp递推式 */
        // dp[i] = Math.max(dp[i - 3] + nums[i], Math.max(dp[i - 1], dp[i - 2]));
        // 注意 max(dp[i-1],dp[i-2])==dp[i-1] 恒成立
        dp[i] = Math.max(dp[i - 3] + nums[i], dp[i - 1]);
      }
      return dp[iMax - 1];
    }
  }
}

注意 dp[i-2] 和 dp[i-1] 的大小关系

没有计算 max(dp[i-1],dp[i-2]) 的必要
dp[i] 的含义就是：在 [0, i] 间屋子里，所能取得的最大值
因此
- dp[i-2] = max([0~i-2])
- dp[i-1] = max([0~i-1,i-2])
显然 dp[i-1] = max(dp[i-2],nums[i-2])
因此 max(dp[i-1],dp[i-2])==dp[i-1] 恒成立

#213 打家劫舍II

环形哦。
其实就是分两次来动态规划
[0, n-2] 和 [1, n-1]—— 错位的两次
- 注意，在初始考虑鲁棒性的时候，两次动态规划的鲁棒性都要考虑到哦。
有的题目是，方向相反的两次 —— 一次左 ➔ 右 —— 一次右 ➔ 左

package Order300;

public class T213_house_robber_ii {

  public static void main(String[] args) {
    System.out.println(new Solution().rob(new int[] { 1, 2, 1, 1 })); // -> 3
  }

  static class Solution {

    public int rob(int[] nums) {
      /* 鲁棒性 特殊条件 输入为空 */
      if (nums == null || nums.length == 0) {
        return 0;
      }
      int iMax = nums.length;
      /* 鲁棒性 特殊条件 仅有一间房 */
      if (iMax == 1) {
        return nums[0];
      }
      /* 鲁棒性 特殊条件 仅有两间房 */
      if (iMax == 2) {
        return Math.max(nums[0], nums[1]);
      }

      int dp_a[] = new int[iMax]; // 0~n-2
      int dp_b[] = new int[iMax]; // 1~n-1
      dp_a[0] = nums[0];
      dp_a[1] = Math.max(nums[0], nums[1]);
      for (int i = 2; i < iMax - 1; i++) {
        dp_a[i] = Math.max(dp_a[i - 2] + nums[i], dp_a[i - 1]);
      }
      dp_b[1] = nums[1];
      dp_b[2] = Math.max(nums[1], nums[2]);
      for (int i = 3; i < iMax; i++) {
        dp_b[i] = Math.max(dp_b[i - 2] + nums[i], dp_b[i - 1]);
      }
      return Math.max(dp_a[iMax - 2], dp_b[iMax - 1]);
    }
  }
}

#337 打家劫舍III

`T337_house_robber_iii.java` 代码备份

讲得好的题解链接
这个代码是可运行的。
之后的分段讲解的代码，复制粘贴以后是不能直接运行的。

// 整个文件的代码太长了，替换换行和空格把程序压缩成一行。点击代码框右上角可以直接复制
// 粘贴到IDE以后，自动格式化一下，差不多也就能看了 /手动狗头
// 下面会分段讲解算法。
package Order300; import java.util.HashMap; import BaseNode.TreeNode; public class T337_house_robber_iii { public static void main(String[] args) { TreeNode root = new TreeNode(); root .setVal(4) .setLeft(TreeNode.from(1).setLeft(TreeNode.from(2))) .setRight(TreeNode.from(0).setLeft(TreeNode.from(3))); /* -> 9 */ System.out.printf("%d ", new Solution_me_梦中get终极算法().rob(root)); System.out.printf("%d ", new Solution_other().rob(root)); System.out.printf("%d ", new Solution_me_最优子结构递归().rob(root)); System.out.printf("%d ", new Solution_me_最优子结构记忆化().rob(root)); System.out.printf("%d ", new Solution_me_终极算法().rob(root)); System.out.println(); root = TreeNode .from(3) .setLeft(TreeNode.from(2).setRight(TreeNode.from(3))) .setRight(TreeNode.from(3).setRight(TreeNode.from(1))); /* -> 7 */ System.out.printf("%d ", new Solution_me_梦中get终极算法().rob(root)); System.out.printf("%d ", new Solution_other().rob(root)); System.out.printf("%d ", new Solution_me_最优子结构递归().rob(root)); System.out.printf("%d ", new Solution_me_最优子结构记忆化().rob(root)); System.out.printf("%d ", new Solution_me_终极算法().rob(root)); System.out.println(); root = TreeNode .from(3) .setLeft( TreeNode.from(4).setLeft(TreeNode.from(1)).setRight(TreeNode.from(3)) ) .setRight(TreeNode.from(5).setRight(TreeNode.from(1))); /* -> 9 */ System.out.printf("%d ", new Solution_me_梦中get终极算法().rob(root)); System.out.printf("%d ", new Solution_other().rob(root)); System.out.printf("%d ", new Solution_me_最优子结构递归().rob(root)); System.out.printf("%d ", new Solution_me_最优子结构记忆化().rob(root)); System.out.printf("%d ", new Solution_me_终极算法().rob(root)); System.out.println(); } /** 算法思想是好的，但是代码设计不够优秀。 * BUG 在于 * 如果 root 不偷，则儿子可偷可不偷！ * 并不是说 root 不偷，儿子就一定得 偷 才能是最大的！ * * BUG就不修复了，放着吧。 * 修复了的见 Solution_me_终极算法 */ static class Solution_me_梦中get终极算法 { public int rob(TreeNode root) { /* 鲁棒性 特殊条件 输入过少 */ if (root == null) { return 0; } return Math.max(robSubTree(root, true), robSubTree(root, false)); } private int robSubTree(TreeNode root, boolean isRootSelected) { /* 仔细看 我的程序 保证了 robSubTree 的 root 不是 null */ if (root == null) throw new RuntimeException( "robSubTree's root shouldn't be NULL !!!" ); if (isRootSelected) { return ( root.val + (root.left == null ? 0 : robSubTree(root.left, !isRootSelected)) + (root.right == null ? 0 : robSubTree(root.right, !isRootSelected)) ); } else { return ( (root.left == null ? 0 : robSubTree(root.left, !isRootSelected)) + (root.right == null ? 0 : robSubTree(root.right, !isRootSelected)) ); } } } /** 通过优化为 最优子结构 来优化动态规划路径。 * 最优子结构 是 7个节点 的 一颗爷孙二叉树 * result = max( * val(root) + * rob(root.left.left) + rob(root.left.right) + * rob(root.right.left) + rob(root.right.right) * , * rob(root.left) + rob(root.right); * ) * * 复杂度太高，超时了哈哈哈哈 */ static class Solution_me_最优子结构递归 { /** 安全的取值函数 —— 无惧输入为 null */ private int val(TreeNode node) { return (node == null) ? 0 : node.val; } /** 安全的取值函数 —— 无惧输入为 null */ private TreeNode getSon(TreeNode node, String who) { return (node == null) ? null : ("left".equals(who) ? node.left : node.right); } public int rob(TreeNode root) { /* 鲁棒性 特殊条件 输入过少 */ if (root == null) { return 0; } /* 可能性一 去 爷爷家 和 四个孙子的小区 */ int get_5 = val(root) + rob(getSon(getSon(root, "left"), "right")) + rob(getSon(getSon(root, "left"), "left")) + rob(getSon(getSon(root, "right"), "left")) + rob(getSon(getSon(root, "right"), "right")); /* 可能性二 去 两个儿子的小区 */ int get_2 = rob(getSon(root, "left")) + rob(getSon(root, "right")); return Math.max(get_5, get_2); } } /** * 问题结构是数，所以dp不方便用数组，就用 HashMap 存储 node:TreeNode 和 rob(node) 的对应关系。 * 效率：3ms => 54.44% **/ static class Solution_me_最优子结构记忆化 { /** 安全的取值函数 —— 无惧输入为 null */ private int val(TreeNode node) { return (node == null) ? 0 : node.val; } /** 安全的取值函数 —— 无惧输入为 null */ private TreeNode getSon(TreeNode node, String who) { return (node == null) ? null : ("left".equals(who) ? node.left : node.right); } public int rob(TreeNode root) { return memorizedRob(root, new HashMap<TreeNode, Integer>()); } private int memorizedRob( TreeNode root, HashMap<TreeNode, Integer> dpTable ) { /* 鲁棒性 特殊条件 输入过少 */ if (root == null) { return 0; } if (dpTable.containsKey(root)) { return dpTable.get(root); } /* 可能性一 去 爷爷家 和 四个孙子的小区 */ int lr = memorizedRob(getSon(getSon(root, "left"), "right"), dpTable); int ll = memorizedRob(getSon(getSon(root, "left"), "left"), dpTable); int rl = memorizedRob(getSon(getSon(root, "right"), "left"), dpTable); int rr = memorizedRob(getSon(getSon(root, "right"), "right"), dpTable); int get_5 = val(root) + lr + ll + rl + rr; /* 可能性二 去 两个儿子的小区 */ int get_2 = memorizedRob(getSon(root, "left"), dpTable) + memorizedRob(getSon(root, "right"), dpTable); int robRoot = Math.max(get_5, get_2); dpTable.put(root, robRoot); return robRoot; } } /* 淦 终极解法 感觉和我一开始的想法完全一样啊，只是他代码设计的比我好 呜呜呜 */ /** * 分两种情况： * - 偷自己 ：val(root) + rob(left,false) + rob(right,false) * - 不偷自己 ：rob(left,true) + rob(right,true) * * 这样的递归不存在 重复子问题 ,也就不需要 HashMap 记忆化来优化了 * 效率 0ms => 100% */ static class Solution_me_终极算法 { public int rob(TreeNode root) { int[] result = rubAll(root); return Math.max(result[0], result[1]); } /** * out[0] : 偷root * out[1] : 不偷root */ private int[] rubAll(TreeNode root) { if (root == null) { return new int[2]; } /* root 肯定不是 null 也就不需要安全性输入了 */ int[] left = rubAll(root.left); int[] right = rubAll(root.right); return new int[] { /* 偷了 root 则儿子只能不偷 */ root.val + left[1] + right[1], /* 没偷 root 则儿子可偷可不偷，要大的！ */ Math.max(left[0], left[1]) + Math.max(right[0], right[1]), }; } } /** 大佬的终极算法代码实现 */ static class Solution_other { public int rob(TreeNode root) { int[] result = robInternal(root); return Math.max(result[0], result[1]); } public int[] robInternal(TreeNode root) { if (root == null) return new int[2]; int[] result = new int[2]; int[] left = robInternal(root.left); int[] right = robInternal(root.right); result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); result[1] = left[0] + right[0] + root.val; return result; } } }

睡着前想到的算法 —— 终极算法 —— 有 bug

之所以称之为终极算法，是因为这个递归路径不存在重复子问题。
不过在代码的设计上有所纰漏，写出了逻辑 Bug
正确的思路是：
- 如果 root 节点要打劫 —— 那么儿子节点就不能被打劫
- 如果 root 节点不打劫 —— 那么儿子节点打不打劫都可以 —— 都要计算并取最大值
错误的代码如下。你能看出我的bug么～🤪🤪🤪

class Solution_me_梦中get终极算法 {

  public int rob(TreeNode root) {
    /* 鲁棒性 特殊条件 输入过少 */
    if (root == null) {
      return 0;
    }
    return Math.max(robSubTree(root, true), robSubTree(root, false));
  }

  private int robSubTree(TreeNode root, boolean isRootSelected) {
    /* 仔细看 我的程序 保证了 robSubTree 的 root 不是 null */
    if (root == null) throw new RuntimeException(
      "robSubTree's root shouldn't be NULL !!!"
    );
    if (isRootSelected) {
      return (
        root.val +
        (root.left == null ? 0 : robSubTree(root.left, !isRootSelected)) +
        (root.right == null ? 0 : robSubTree(root.right, !isRootSelected))
      );
    } else {
      /* bug here */
      return (
        (root.left == null ? 0 : robSubTree(root.left, !isRootSelected)) +
        (root.right == null ? 0 : robSubTree(root.right, !isRootSelected))
      );
      /* it should be 
        return (
          (
            (root.left == null)
              ? 0
              : Math.max(
                robSubTree(root.left, true),
                robSubTree(root.left, false)
              )
          ) +
          (
            (root.right == null)
              ? 0
              : Math.max(
                robSubTree(root.right, true),
                robSubTree(root.right, false)
              )
          )
          );
        */
    }
  }
}

递归 —— 最优子结构

这里有几个术语需要了解一下 —— 这篇博客讲得很好
- 动态规划
- 自顶向下
- 自底向上
- 最优子结构
- 重复子问题
- 记忆化
本题的最优子结构考虑如下：
- 考虑 7个节点的一颗爷孙二叉树（即深度为2的_满二叉树）
- 如果 root 节点被选中，那么就不能选择儿子节点，但是可以选所有的孙子们
- 如果 root 节点未选中，那么考虑所有的儿子节点
- 最终答案应该是 root 在选中与否的两种可能中取最大值。
- 写成伪代码就是这样：
int rob (TreeNode root){
return max(
val(root) +
rob(root.left.left) + rob(root.left.right) +
rob(root.right.left) + rob(root.right.right)
,
rob(root.left) + rob(root.right);
)
}
代码实现如下

/**
   * 最优子结构 是 7个节点 的 一颗爷孙二叉树
   * result = max(
   *  val(root) +
   *  rob(root.left.left) + rob(root.left.right) +
   *  rob(root.right.left) + rob(root.right.right)
   *  ,
   *  rob(root.left) + rob(root.right);
   * )
   *
   * 复杂度太高，超时了哈哈哈哈
   */
static class Solution_me_最优子结构递归 {

  /** 安全的取值函数 —— 无惧输入为 null */
  private int val(TreeNode node) {
    return (node == null) ? 0 : node.val;
  }

  /** 安全的取值函数 —— 无惧输入为 null */
  private TreeNode getSon(TreeNode node, String who) {
    return (node == null)
      ? null
      : ("left".equals(who) ? node.left : node.right);
  }

  public int rob(TreeNode root) {
    /* 鲁棒性 特殊条件 输入过少 */
    if (root == null) {
      return 0;
    }
    /* 可能性一 去 爷爷家 和 四个孙子的小区 */
    int get_5 =
      val(root) +
      rob(getSon(getSon(root, "left"), "right")) +
      rob(getSon(getSon(root, "left"), "left")) +
      rob(getSon(getSon(root, "right"), "left")) +
      rob(getSon(getSon(root, "right"), "right"));
    /* 可能性二 去 两个儿子的小区 */
    int get_2 = rob(getSon(root, "left")) + rob(getSon(root, "right"));
    return Math.max(get_5, get_2);
  }
}

最优子结构 —— `HashMap`记忆化

为了避免计算重复子问题，我们一般的选择是用dp数组记录子问题答案
但是这个题目的问题结构不是线性的，而是树形的，因此不方便用数组
我们改用HashMap<parms,reuslt>来直接地保存子问题及其答案

/**
   * 问题结构是数，所以dp不方便用数组，就用 HashMap 存储 node:TreeNode 和 rob(node) 的对应关系。
   * 效率：3ms => 54.44%
   **/
class Solution_me_最优子结构记忆化 {

  /** 安全的取值函数 —— 无惧输入为 null */
  private int val(TreeNode node) {
    return (node == null) ? 0 : node.val;
  }

  /** 安全的取值函数 —— 无惧输入为 null */
  private TreeNode getSon(TreeNode node, String who) {
    return (node == null)
      ? null
    : ("left".equals(who) ? node.left : node.right);
  }

  public int rob(TreeNode root) {
    return memorizedRob(root, new HashMap<TreeNode, Integer>());
  }

  private int memorizedRob(
  TreeNode root,
   HashMap<TreeNode, Integer> dpTable
  ) {
    /* 鲁棒性 特殊条件 输入过少 */
    if (root == null) {
      return 0;
    }
    if (dpTable.containsKey(root)) {
      return dpTable.get(root);
    }
    /* 可能性一 去 爷爷家 和 四个孙子的小区 */
    int lr = memorizedRob(getSon(getSon(root, "left"), "right"), dpTable);
    int ll = memorizedRob(getSon(getSon(root, "left"), "left"), dpTable);
    int rl = memorizedRob(getSon(getSon(root, "right"), "left"), dpTable);
    int rr = memorizedRob(getSon(getSon(root, "right"), "right"), dpTable);
    int get_5 = val(root) + lr + ll + rl + rr;
    /* 可能性二 去 两个儿子的小区 */
    int get_2 =
      memorizedRob(getSon(root, "left"), dpTable) +
      memorizedRob(getSon(root, "right"), dpTable);
    int robRoot = Math.max(get_5, get_2);
    dpTable.put(root, robRoot);
    return robRoot;
  }
}

终极递归 —— 消除重复子问题

重新设计递归路径
这个以数组作为函数返回值并参与递归的设计，很有趣

/**
   * 分两种情况：
   * - 偷自己 ：val(root) + rob(left,false) + rob(right,false)
   * - 不偷自己 ：rob(left,true) + rob(right,true)
   *
   * 这样的递归不存在 重复子问题 ,也就不需要 HashMap 记忆化来优化了
   * 效率 0ms => 100%
   */
class Solution_me_终极算法 {

  public int rob(TreeNode root) {
    int[] result = rubAll(root);
    return Math.max(result[0], result[1]);
  }

  /**
     * out[0] : 偷root
     * out[1] : 不偷root
     */
  private int[] rubAll(TreeNode root) {
    if (root == null) {
      return new int[2];
    }
    /* root 肯定不是 null 也就不需要安全性输入了 */
    int[] left = rubAll(root.left);
    int[] right = rubAll(root.right);
    return new int[] {
      /* 偷了 root 则儿子只能不偷 */
      root.val + left[1] + right[1],
      /* 没偷 root 则儿子可偷可不偷，要大的！ */
      Math.max(left[0], left[1]) + Math.max(right[0], right[1]),
    };
  }
}

小贴士

我觉得自己写的安全化输入真好用🤪

/** 安全的取值函数 —— 无惧输入为 null */
private int val(TreeNode node) {
  return (node == null) ? 0 : node.val;
}

/** 安全的取值函数 —— 无惧输入为 null */
private TreeNode getSon(TreeNode node, String who) {
  return (node == null)
    ? null
    : ("left".equals(who) ? node.left : node.right);
}

#53 最大子序和

可以用双指针 `0ms => 100%` 代码如下

left、right 都从左至右遍历
循环中，right++，滑动窗口添加新节点，并求出当前滑动窗口的 sum
然后调整滑动窗口若 [left].val < 0 或 sum([left,right]) < 0
- 则 left++ —— 同时 ——被原来的 left 指向的节点值从滑动窗口里移出
- 别忘了首要条件 left < rigjt
每当 right、left、sum 整理过一次后，更新保存的 maxSubSum
其实这个算法也会摇出 1ms，但是摇出 0ms 的实验概率比动态规划高不少。
- 我动态规划就没摇出 0ms 过，实验概率为 0%。

/**
   * left,right 都 从左至右 遍历
   * right++，滑动窗口添加新节点，并求出当前滑动窗口的 sum
   * 若 [left].val < 0 或 sum([left,right]) < 0 则 left++
   * - (同时被原来的 left 指向的元素移出滑动窗口)
   * 每当 right,left,sum 整理过一次后，更新保存的 maxSubSum
   **/
  class Solution_指针 {

    public int maxSubArray(int[] nums) {
      int maxSum = nums[0]; // 从 起点至今 的所有 滑动窗口 的 maxSum
      int sum = 0; // 当前 滑动窗口 的 sum
      int iMax = nums.length;
      for (int right = 0, left = 0; right < iMax; right++) {
        sum += nums[right];
        while (left < right && (nums[left] < 0 || sum < 0)) {
          sum -= nums[left++];
        }
        maxSum = Math.max(sum, maxSum);
      }
      return maxSum;
    }
  }

可以用动态规划 `1ms => 94.80%` 代码如下

// url: https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
class Solution {
  public int maxSubArray(int[] nums) {
    int pre = 0, maxAns = nums[0];
    for (int x : nums) {
      pre = Math.max(pre + x, x);
      maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
  }
}

可以用分治——线段树题解链接

线段树 看着是挺棒挺有趣的一个数据结构
不过不是今天的重点。就先算了。

自己用动态规划

preSubSum：包含 前一个元素 的所有子数组的 maxSubArraySum
maxSubSum：从 起点至今 的所有子数组的 maxSubArraySum
preSubSum = Math.max(preSubSum + x, x);——新的preSubSum：
- 要么是之前的preSubSum加上当前节点值
- 要么是当前节点值
- 谁大要谁
什么时候（preSubSum加上当前节点值）会大于（当前节点值）？
x+y > y <=> x > 0
所以，其实preSubSum = Math.max(preSubSum + x, x);可以改写为
- preSubSum = preSubSum > 0 ? preSubSum + x : x
- 不过即使改成这样，也还是 1ms => 94.81%

package Order300;

public class T53_maximum_subarray {

  public static void main(String[] args) {
    System.out.println(
      new Solution().maxSubArray(new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 })
    );
  }

  static class Solution {

    public int maxSubArray(int[] nums) {
      /* DP解决，不过因为 f(x) 仅和 f(x-1) 有关，所以找个变量保存 f(x-1) 就好了 */
      int preSubSum = 0; // 包含 前一个元素 的所有子数组的maxSubArraySum
      int maxSubSum = nums[0]; // 从 起点至今 的所有子数组的maxSubArraySum
      for (int x : nums) {
        preSubSum = Math.max(preSubSum + x, x);
        maxSubSum = Math.max(maxSubSum, preSubSum);
        // System.out.printf("%d\t%d\t%d\n", x, preSubSum, maxSubSum);
      }
      return maxSubSum;
    }
  }
}

#32 最长有效括号

这题处理动态规划，也有别的解法。但是以后再做
今天的就是全力搞懂动态规划
等从头刷到尾，遇到这题的时候，再尝试动态规划以外的解法
有个骚解法：
- 对字符串遍历，进行括弧有效性验证，
- 记录最大的有效长度。
- 同样的方式，倒序再来一次。
- 取两次遍历的结果最大值。
- 时间复杂度 2*s.length；

public class Solution {

  public int longestValidParentheses(String s) {
    char[] chars = s.toCharArray();
    return Math.max(
      calc(chars, 0, 1, chars.length, '('),
      calc(chars, chars.length - 1, -1, -1, ')')
    );
  }

  private static int calc(char[] chars, int i, int flag, int end, char cTem) {
    int max = 0, sum = 0, currLen = 0, validLen = 0;
    for (; i != end; i += flag) {
      sum += (chars[i] == cTem ? 1 : -1);
      currLen++;
      if (sum < 0) {
        max = max > validLen ? max : validLen;
        sum = 0;
        currLen = 0;
        validLen = 0;
      } else if (sum == 0) {
        validLen = currLen;
      }
    }
    return max > validLen ? max : validLen;
  }
}

关键：dp[i] 的含义：包含 s[i] 的字符串，其最长有效括号的子串长度。
- 也就是说，以双指针理解，dp[i]意为着 right == i && left < right 的窗口上，最长有效括号的长度。
- 因为这个滑动窗口的值，不仅仅和 left、right有关，所以不能用双指针写。
  - 但是可以用栈来写
- 动态规划数组，其实就是对 right == i && left < right 的窗口的值的保存。
状态转移 分情况考虑
......( —— dp[i] := 0
......) 分 A、B 两种情况
A ......() —— dp[i] := dp[i-2] + 2 —— when (i-2>0)
B ......)) —— 不妨假设为 ...?(..)) —— 再分为 C、D 两种情况
- (..) 可以为 "空"
- ...?
  - ... 可以是任意长度字符串，包括"空"
  - ?是一个 ( 或者是一个 )
D ...)(..)) —— dp[i] := 0
C ...((..)) —— dp[i] = dp["..."] + dp["(..)"] + 2
- dp["(..)"] 即为 dp[i-1] —— 显然i-1 > 0
- dp["..."] 即为 dp[ i-(dp[i-1]+2) ] —— 不能确定i-(dp[i-1]+2) > 0
我的代码中，用 preLen 表示 dp["(..)"] 也就是 dp[i-1]

package Order300;

public class T32_longest_valid_parentheses {

  /** 本地调试时用于打印 s 和 dp */
  static void printDP(String s, int[] dp) {
    StringBuilder sdp = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
      System.out.print(s.charAt(i));
      System.out.print(" ");
      sdp.append(String.valueOf(dp[i]));
      sdp.append(" ");
    }
    System.out.println();
    System.out.println(sdp.toString());
  }

  public static void main(String[] args) {
    // System.out.println(new Solution().longestValidParentheses("()")); // -> 2
    // System.out.println(new Solution().longestValidParentheses("(")); // -> 0
    // System.out.println(new Solution().longestValidParentheses(")")); // -> 0
    // System.out.println(new Solution().longestValidParentheses("(()")); // -> 2
    // System.out.println(new Solution().longestValidParentheses("(())))")); // -> 4
    System.out.println(new Solution().longestValidParentheses(")(())()))")); // -> 6
    System.out.println(
      new Solution_leecode().longestValidParentheses(")(())()))")
    ); // -> 6
    // System.out.println(new Solution().longestValidParentheses("(()())()))")); // -> 8
  }

  static class Solution {

    public int longestValidParentheses(String s) {
      int iMax = s.length();
      /* 鲁棒性 特殊条件 输入太短 */
      if (s == null || iMax < 2) {
        return 0;
      }
      int[] dp = new int[iMax];
      dp[0] = 0;
      int maxAnswer = 0;
      if ("()".equals(s.substring(0, 2))) {
        maxAnswer = dp[1] = 2;
      } else {
        dp[1] = 0;
      }
      for (int i = 2; i < iMax; i++) {
        if (s.charAt(i) == '(') {
          /* ......( */
          dp[i] = 0;
        } else if (s.charAt(i - 1) == '(') {
          /* ......() */
          dp[i] = dp[i - 2] + 2;
        } else {
          /* ......)) */
          int preLen = dp[i - 1]; // prelen 是不是 0 都OK
          /* 考虑形如 ....((..)) */
          if (i - (preLen + 1) >= 0 && s.charAt(i - (preLen + 1)) == '(') {
            if (i - (preLen + 2) >= 0) {
              /* 如果是 ....((..)) */
              dp[i] = preLen + 2 + dp[i - (dp[i - 1] + 2)];
            } else {
              /* 否则是 ((..)) */
              dp[i] = preLen + 2;
            }
          } else {
            /* 考虑形如 ....)(..)) */
            dp[i] = 0;
          }
        }
        maxAnswer = Math.max(maxAnswer, dp[i]);
      }
      printDP(s, dp);
      return maxAnswer;
    }
  }

  /**
   * 官方的写法比我简洁好多。
   * 可以通过函数 printDP(s,dp) 看出，对于 ")(())()))" 我和官方写法，dp数组值是完全一样的。
   * 再仔细看看代码，感觉官方写法只是省略了 dp[i] = 0 的赋值。
   * 因为Java的数组默认值是0的，所以可以省略，但是没必要。我的代码中还是保留吧。
   **/
  static class Solution_leecode {

    public int longestValidParentheses(String s) {
      int maxans = 0;
      int[] dp = new int[s.length()];
      for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
          if (s.charAt(i - 1) == '(') {
            dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
          } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
            dp[i] =
              dp[i - 1] +
              ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) +
              2;
          }
          maxans = Math.max(maxans, dp[i]);
        }
      }
      printDP(s, dp);
      return maxans;
    }
  }
}

#42 接雨水

这题还可以用单调栈或者双指针解决，效果更好。
动态规划思路分析
- iMax 输入的数组长度
- height:int[iMax] —— height[i] 表示 i 号位这一格有多高
- val:int[iMax] —— val[i] 表示 i 号位这一格能存多少水
- leftMax:int[iMax] —— leftMax[i] 表示 i 号位左边的最大值
- rightMax:int[iMax] —— 类似于 leftMax:int[iMax]
- val[i] = Math.min( leftMax[i-1] , rightMax[i+1] ) - height[i]
  - 负数则向上补至0
通过动态规划生成 leftMax 和 rightMax 这两个数组即可。
我的疏忽点：
- leftMax 初值 leftMax[0] := height[0];
  
  rightMax 初值 rightMax[iMax-1] := height[iMax-1];
- leftMax 遍历 range(0, iMax, 1)
  rightMax 遍历 range(iMax-2, -1, -1)
效率 2ms => 48.75%

class Solution {

    public int trap(int[] height) {
      /* 鲁棒性 特殊条件 输入太短 */
      if (height == null || height.length < 2) {
        return 0;
      }
      int iMax = height.length;
      int leftMax[] = new int[iMax];
      int rightMax[] = new int[iMax];

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

      // rightMax range(iMax-2, -1, -1)
      rightMax[iMax - 1] = height[iMax - 1];
      for (int i = iMax - 2; i > -1; i--) {
        rightMax[i] = Math.max(height[i], rightMax[i + 1]);
      }
      // for (int i : leftMax) {
        // System.out.print(i);
        // System.out.print(" ");
      // }
      // System.out.println();
      // for (int i : height) {
        // System.out.print(i);
        // System.out.print(" ");
      // }
      // System.out.println();
      // for (int i : rightMax) {
        // System.out.print(i);
        // System.out.print(" ");
      // }
      // System.out.println();

      // val range(1, iMax-1, 1)
      int sum = 0;
      int single = 0;
      // System.out.print("  ");
      for (int i = 1; i < iMax - 1; i++) {
        single = Math.min(leftMax[i - 1], rightMax[i + 1]) - height[i];
        // System.out.print(single > 0 ? single : "-");
        // System.out.print(" ");
        sum += (single > 0 ? single : 0);
      }
      // System.out.println();
      return sum;
    }
  }

#44 通配符匹配

答案看懂了，但是自己还是想不出来。
效率够低的呢，43ms => 16.03%
感觉动态规划应该是
- 数据结构设计难度较高 —— 状态转移方程不容易想清楚
- 代码实现较简单 —— 从状态转移到代码实现，有点声明式编程的感觉
- 时间复杂度正常 —— 一方面避免了过多的分支和回溯、复杂度不至于很高 —— 另一方面来说至少要遍历完dp数组、复杂度不至于很低
- 空间复杂度正常 —— 类似与时间复杂度 —— 成也DP数组、败也DP数组

package Order300;

public class T44_wildcard_matching {

  public static void main(String[] args) {
    System.out.println(new Solution().isMatch("adceb", "*a*b"));
  }

  static class Solution {

    public boolean isMatch(String s, String p) {
      int sMax = s.length();
      int pMax = p.length();

      /* 特别的，在 Java 中 boolean[] 初始化，元素的值是 false */
      /* dp[si][pi] 意为 s[:si) 与 p[:pi) 是否匹配成功 */
      boolean[][] dp = new boolean[sMax + 1][pMax + 1];

      /**
       * dp起点 dp[0][1:pMax+1) := false 且 dp[1:sMax+1)[0] := false
       * 由于在 Java 中 boolean[] 初始化，元素的值是 false，所以这一起点赋值可以在代码中省略
       *
       * dp起点 空s 和 空p 匹配成功 —— dp[0][0] = true;
       * dp起点 p 的开头如果有连续的 n 个 '*' 那么要设置这些 '*' 都匹配空作为起点
       **/
      dp[0][0] = true;
      for (int pi = 1; pi <= pMax; pi++) {
        if (p.charAt(pi - 1) == '*') dp[0][pi] = true; else break;
      }

      /* dp递推开始 */
      for (int si = 1; si <= sMax; si++) {
        for (int pi = 1; pi <= pMax; pi++) {
          if (p.charAt(pi - 1) == '*') {
            /* 这个 * 可以用于匹配空 也可以用于匹配s中一个字符 */
            dp[si][pi] =
              /* 如果这个 '*' 匹配了空 那么，当前状态就和没用过这个 pi 位的 pi-1 一样 */
              dp[si][pi - 1] ||
              /* 如果这个 '*' 匹配了当前s 那么，当前状态就和不需要匹配这个 si 位的 si-1 一样 */
              dp[si - 1][pi];
          } else if (
            p.charAt(pi - 1) == '?' || s.charAt(si - 1) == p.charAt(pi - 1)
          ) {
            /* 如果是 p[pi-1] 是 '?' 或者 s[si-1]==p[pi-1] 的话，那么当前状态就和不需要用这个 pi 位 匹配这个 si 位的 dp[si-1][pi-1] 一样 */
            dp[si][pi] = dp[si - 1][pi - 1];
          }
        }
      }

      return dp[sMax][pMax];
    }
  }
}

#62 不同路径

初中数学竞赛学过。秒了。不想解说/手动狗头
dp[0][ni] 均为 1 —— ni in range[ 0, n )
dp[mi][0] 均为 1 —— mi in range[ 0, m )
mi in range[ 1 , m ) —— ni in range[ 1, n ) —— dp[mi][ni] = dp[mi - 1][ni] + dp[mi][ni - 1]
这个dp数组可以被优化为一个一维数组 new int[Math.min(m,n)]
整个题都可以直接推导出数学公式然后直接算出答案

package Order300;

public class T62_unique_paths {

  public static void main(String[] args) {
    System.out.println(new Solution().uniquePaths(7, 3)); // -> 28
  }

  static class Solution {

    public int uniquePaths(int m, int n) {
      int dp[][] = new int[m][n];
      // dp[0][0] = 0;
      for (int mi = 0; mi < m; mi++) {
        dp[mi][0] = 1;
      }
      for (int ni = 0; ni < n; ni++) {
        dp[0][ni] = 1;
      }

      for (int mi = 1; mi < m; mi++) {
        for (int ni = 1; ni < n; ni++) {
          dp[mi][ni] = dp[mi - 1][ni] + dp[mi][ni - 1];
        }
      }
      return dp[m - 1][n - 1];
    }
  }
}

#63 不同路径II

鲁棒性 特殊条件 —— 输入太少 —or— 起点或终点有障碍物
起点初始化：
- m:0 的这一行，如果遇到了障碍物，则后面的都是0，不用继续赋初值1了，break就好
- n:0 的这一列，如果遇到了障碍物，则后面的都是0，不用继续赋初值1了，break就好
dp遍历中：
- 如果当前位置有障碍物 则 dp[mi][ni] := 0 赋值可省略
- 否则，dp[mi][ni] = dp[mi - 1][ni] + dp[mi][ni - 1]
优化方向，同上一题，这题的dp数组也能优化成一个一维数组 new int[Math.min(m,n)]

package Order300;

public class T63_unique_paths_ii {

  static class Solution {

    /**
     * m := obstacleGrid.length
     * n := obstacleGrid[i].length
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
      /* 鲁棒性 特殊条件 输入太少 或者 起点或终点有障碍物 */
      if (
        obstacleGrid == null ||
        obstacleGrid.length < 1 ||
        obstacleGrid[0] == null ||
        obstacleGrid[0].length < 1 ||
        obstacleGrid[0][0] == 1 ||
        obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1
      ) {
        return 0;
      }
      int m = obstacleGrid.length;
      int n = obstacleGrid[0].length;

      int dp[][] = new int[m][n];
      for (int mi = 0; mi < m; mi++) {
        if (obstacleGrid[mi][0] != 1) {
          dp[mi][0] = 1;
        } else {
          break;
        }
      }
      for (int ni = 0; ni < n; ni++) {
        if (obstacleGrid[0][ni] != 1) {
          dp[0][ni] = 1;
        } else {
          break;
        }
      }

      for (int mi = 1; mi < m; mi++) {
        for (int ni = 1; ni < n; ni++) {
          if (obstacleGrid[mi][ni] == 0) {
            dp[mi][ni] = dp[mi - 1][ni] + dp[mi][ni - 1];
          }
        }
      }
      return dp[m - 1][n - 1];
    }
  }
}

#64 最小路径和

dp的初始和递推遍历需要稍微更改得符合题意，就好了。

package Order300;

public class T64_minimum_path_sum {

  public static void main(String[] args) {
    System.out.println(
      new Solution()
      .minPathSum(
          new int[][] {
            new int[] { 1, 3, 1 },
            new int[] { 1, 5, 1 },
            new int[] { 4, 2, 1 },
          }
        )
    ); // -> 7
  }

  static class Solution {

    public int minPathSum(int[][] grid) {
      /* 鲁棒性 特殊条件 输入太少 */
      if (
        grid == null || grid.length < 1 || grid[0] == null || grid[0].length < 1
      ) {
        return 0;
      }
      int m = grid.length;
      int n = grid[0].length;
      int dp[][] = new int[m][n];

      dp[0][0] = grid[0][0];
      for (int mi = 1; mi < m; mi++) {
        dp[mi][0] = dp[mi - 1][0] + grid[mi][0];
      }
      for (int ni = 1; ni < n; ni++) {
        dp[0][ni] = dp[0][ni - 1] + grid[0][ni];
      }

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

#139 单词拆分

我原先的思路是:
对于 String s 应有 int iMax = s.length();
有dp数组两个
- boolean start[] = new int[iMax+1] —— True 则说明s[i]是子串匹配的起点
- boolean end[] = new int[iMax+1] —— True 则说明s[i-1]是子串匹配的终点
然后开始写代码，感觉，其实 start 真没什么用
（然后拉肚子了，回来就搬电脑去上课了，等上课回来，就忘了）
后来照着 start 去写，怎么写都搞不明白，自己都写不明白。
最后看答案才想起来。不需要 start 的。
关键：↓↓↓
动态规划中的子问题划分——此处的子问题是指，
相对于在整个 String s 上寻求匹配，
我们暂时只需要知道 s[0,i] 上的匹配能否成功。
也就是说，我们只需要 end 。
而不是一定要去建立一个完整的 start[] end[] 表来储存整个字符串各处局部匹配的结果。

package Order300;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class T139_word_break {

  public static void main(String[] args) {
    System.out.println(
      new Solution()
      .wordBreak(
          "catsandog",
          Arrays.asList(
            new String[] { "cats", "dog", "sand", "and", "cat", "cee" }
          )
        )
    );
  }

  // TODO 自己再做一遍嗷！
  // ！！！就是不需要 start 集 只需要 end 集就够了！start 并不重要！
  static class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
      int iMax = s.length();
      Set<String> wordDictSet = new HashSet<>(wordDict);
      boolean[] dp = new boolean[iMax + 1];
      dp[0] = true;
      for (int i = 1; i <= iMax; i++) {
        // 检测分割点
        for (int j = 0; j < i; j++) {
          if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
            dp[i] = true;
            break;
          }
        }
      }
      return dp[iMax];
    }
  }
}

#198 打家劫舍

修改原题 左右各两家

注意 dp[i-2] 和 dp[i-1] 的大小关系

#213 打家劫舍II

#337 打家劫舍III

T337_house_robber_iii.java 代码备份

睡着前想到的算法 —— 终极算法 —— 有 bug

递归 —— 最优子结构

最优子结构 —— HashMap记忆化

终极递归 —— 消除重复子问题

小贴士

#53 最大子序和

可以用 双指针 0ms => 100% 代码如下

可以用 动态规划 1ms => 94.80% 代码如下

可以用 分治——线段树 题解链接

自己用 动态规划

#32 最长有效括号

#42 接雨水

#44 通配符匹配

#62 不同路径

#63 不同路径II

#64 最小路径和

#139 单词拆分

修改原题左右各两家

`T337_house_robber_iii.java` 代码备份

最优子结构 —— `HashMap`记忆化

可以用双指针 `0ms => 100%` 代码如下

可以用动态规划 `1ms => 94.80%` 代码如下

可以用分治——线段树题解链接

自己用动态规划