区间DP

  • dp[L…R]表示在区间[L…R]范围内的方案数等

    516. 最长回文子序列

    给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

  1. public int longestPalindromeSubseq(String s) {
  2.       int n = s.length();
  3.       // dp[i...j]表示在s[i...j]范围内最长回文子序列的长度
  4.       int[][] dp = new int[n][n];
  6.       // 填dp表
  7.       dp[n - 1][n - 1] = 1;
  9.       for (int i = 0; i < n - 1; i++) {
  10.         dp[i][i] = 1;
  11.         dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 2 : 1;
  12.       }
  14.       // 填dp表中剩余的格子
  15.       for (int i = n - 3; i >= 0; i--) {
  16.         for (int j = i + 2; j < n; j++) {
  17.           if (s.charAt(i) == s.charAt(j)) {
  18.             dp[i][j] = 2 + dp[i + 1][j - 1];
  19.           } else {
  20.             dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
  21.           }
  22.         }
  23.       }
  24.       return dp[0][n - 1];
  25.     }

5. 最长回文子串

  1.  // 在s[L...R]范围内寻找最长回文子串
  2.     public String longestPalindrome(String s) {
  4.       if (s == null || s.length() == 0) {
  5.         return s;
  6.       }
  8.       // 最长子串开始的位置以及跨越的长度
  9.       int start = 0;
  10.       int step = 1;
  12.       int n = s.length();
  13.       // dp[i][j]表示字符串在[i...j]范围内是否是回文字符串
  14.       boolean[][] dp = new boolean[n][n];
  16.       // base case:i==j时，dp为true
  17.       for (int i = 0; i < n; i++) {
  18.         dp[i][i] = true;
  19.       }
  21.       // base case，j==i+1时，看这两个字符是否相等
  22.       for (int i = 0; i < n - 1; i++) {
  23.         dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
  24.         if (dp[i][i + 1]) {
  25.           start = i;
  26.           step = 2;
  27.         }
  28.       }
  30.       // 普遍情况：填dp表格
  31.       for (int i = n - 3; i >= 0; i--) {
  32.         for (int j = i + 2; j < n; j++) {
  33.           // dp[i][j]是否为回文，需要dp[i + 1][j - 1]是回文，且i、j位置的字符相等
  34.           dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
  35.           if (dp[i][j] && j - i + 1 > step) {
  36.             start = i;
  37.             step = j - i + 1;
  38.           }
  39.         }
  40.       }
  41.       return s.substring(start, start + step);
  42.     }

树形DP

  • 树形动态规划与线性动态规划没有本质区别。
  • 其实是套在深度优先遍历里的动态规划(在DFS的过程中实现DP)
  • 子问题就是”一颗子树”，状态一般表示为”以x为根的子树”，决策就是”x的子节点”

    337. 打家劫舍 III

    小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

  1.   class Solution {
  3.     // dp存储的是每个节点在偷/不偷两种情况下能偷到的最大值
  4.     HashMap<TreeNode, int[]> dp = new HashMap<>();
  6.     public int rob(TreeNode root) {
  7.       dp.put(null, new int[]{0, 0});
  8.       dfs(root);
  10.       return Math.max(dp.get(root)[0], dp.get(root)[1]);
  11.     }
  13.     private void dfs(TreeNode root) {
  14.       if (root == null) return;
  15.       dp.put(root, new int[2]);
  17.       dfs(root.left);
  18.       dfs(root.right);
  20.       // 当root不偷的情况下，left和right偷或者不偷都可以
  21.       dp.get(root)[0] = Math.max(dp.get(root.left)[0], dp.get(root.left)[1]) +
  22.           Math.max(dp.get(root.right)[0], dp.get(root.right)[1]);
  23.       // 当root偷的情况下，root的left和right就都不能偷了
  24.       dp.get(root)[1] = dp.get(root.left)[0] + dp.get(root.right)[0] + root.val;
  25.     }
  26.   }

124. 二叉树中的最大路径和

  1. class Solution {
  3.     int maxSum = Integer.MIN_VALUE;
  5.     public int maxPathSum(TreeNode root) {
  6.       dfs(root);
  7.       return maxSum;
  8.     }
  10.     // 计算子树对路径和的贡献值
  11.     private int dfs(TreeNode root) {
  12.       // base case
  13.       if (root == null) {
  14.         return 0;
  15.       }
  16.       // 计算左右子树的贡献值,如果贡献值小于0，就不要
  17.       int leftValue = Math.max(dfs(root.left), 0);
  18.       int rightValue = Math.max(dfs(root.right), 0);
  20.       // 更新maxSum
  21.       maxSum = Math.max(maxSum, leftValue + rightValue + root.val);
  23.       // 当前节点root的贡献值
  24.       return Math.max(leftValue, rightValue) + root.val;
  25.     }
  26.   }

总结

  • 树形DP其实是一种思想，一般使用后续遍历的思想：对于节点root，先遍历左右子树，需要从左右子树中得到什么信息从而丰富root的答案。想要得到的信息就是状态，从左右子树的状态得到root的信息就是状态转移，base case就是需要考虑数的边界问题(叶子节点和一些特殊条件)