class076 区间dp-上【算法】

package class076;
// 让字符串成为回文串的最少插入次数
// 给你一个字符串 s
// 每一次操作你都可以在字符串的任意位置插入任意字符
// 请你返回让s成为回文串的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
public class Code01_MinimumInsertionToPalindrome {
  // 暴力尝试
  public static int minInsertions1(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    return f1(s, 0, n - 1);
  }
  // s[l....r]这个范围上的字符串，整体都变成回文串
  // 返回至少插入几个字符
  public static int f1(char[] s, int l, int r) {
    // l <= r
    if (l == r) {
      return 0;
    }
    if (l + 1 == r) {
      return s[l] == s[r] ? 0 : 1;
    }
    // l...r不只两个字符
    if (s[l] == s[r]) {
      return f1(s, l + 1, r - 1);
    } else {
      return Math.min(f1(s, l, r - 1), f1(s, l + 1, r)) + 1;
    }
  }
  // 记忆化搜索
  public static int minInsertions2(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        dp[i][j] = -1;
      }
    }
    return f2(s, 0, n - 1, dp);
  }
  public static int f2(char[] s, int l, int r, int[][] dp) {
    if (dp[l][r] != -1) {
      return dp[l][r];
    }
    int ans;
    if (l == r) {
      ans = 0;
    } else if (l + 1 == r) {
      ans = s[l] == s[l + 1] ? 0 : 1;
    } else {
      if (s[l] == s[r]) {
        ans = f2(s, l + 1, r - 1, dp);
      } else {
        ans = Math.min(f2(s, l, r - 1, dp), f2(s, l + 1, r, dp)) + 1;
      }
    }
    dp[l][r] = ans;
    return ans;
  }
  // 严格位置依赖的动态规划
  public static int minInsertions3(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    int[][] dp = new int[n][n];
    for (int l = 0; l < n - 1; l++) {
      dp[l][l + 1] = s[l] == s[l + 1] ? 0 : 1;
    }
    for (int l = n - 3; l >= 0; l--) {
      for (int r = l + 2; r < n; r++) {
        if (s[l] == s[r]) {
          dp[l][r] = dp[l + 1][r - 1];
        } else {
          dp[l][r] = Math.min(dp[l][r - 1], dp[l + 1][r]) + 1;
        }
      }
    }
    return dp[0][n - 1];
  }
  // 空间压缩
  // 本题有关空间压缩的实现，可以参考讲解067，题目4，最长回文子序列问题的讲解
  // 这两个题空间压缩写法高度相似
  // 因为之前的课多次讲过空间压缩的内容，所以这里不再赘述
  public static int minInsertions4(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    if (n < 2) {
      return 0;
    }
    int[] dp = new int[n];
    dp[n - 1] = s[n - 2] == s[n - 1] ? 0 : 1;
    for (int l = n - 3, leftDown, backUp; l >= 0; l--) {
      leftDown = dp[l + 1];
      dp[l + 1] = s[l] == s[l + 1] ? 0 : 1;
      for (int r = l + 2; r < n; r++) {
        backUp = dp[r];
        if (s[l] == s[r]) {
          dp[r] = leftDown;
        } else {
          dp[r] = Math.min(dp[r - 1], dp[r]) + 1;
        }
        leftDown = backUp;
      }
    }
    return dp[n - 1];
  }
}

package class076;
// 预测赢家
// 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏
// 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手
// 开始时，两个玩家的初始分值都是 0
// 每一回合，玩家从数组的任意一端取一个数字
// 取到的数字将会从数组中移除，数组长度减1
// 玩家选中的数字将会加到他的得分上
// 当数组中没有剩余数字可取时游戏结束
// 如果玩家 1 能成为赢家，返回 true
// 如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true
// 你可以假设每个玩家的玩法都会使他的分数最大化
// 测试链接 : https://leetcode.cn/problems/predict-the-winner/
public class Code02_PredictTheWinner {
  // 暴力尝试
  public static boolean predictTheWinner1(int[] nums) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    int n = nums.length;
    int first = f1(nums, 0, n - 1);
    int second = sum - first;
    return first >= second;
  }
  // nums[l...r]范围上的数字进行游戏，轮到玩家1
  // 返回玩家1最终能获得多少分数，玩家1和玩家2都绝顶聪明
  public static int f1(int[] nums, int l, int r) {
    if (l == r) {
      return nums[l];
    }
    if (l == r - 1) {
      return Math.max(nums[l], nums[r]);
    }
    // l....r 不只两个数
    // 可能性1 ：玩家1拿走nums[l] l+1...r
    int p1 = nums[l] + Math.min(f1(nums, l + 2, r), f1(nums, l + 1, r - 1));
    // 可能性2 ：玩家1拿走nums[r] l...r-1
    int p2 = nums[r] + Math.min(f1(nums, l + 1, r - 1), f1(nums, l, r - 2));
    return Math.max(p1, p2);
  }
  // 记忆化搜索
  public static boolean predictTheWinner2(int[] nums) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    int n = nums.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        dp[i][j] = -1;
      }
    }
    int first = f2(nums, 0, n - 1, dp);
    int second = sum - first;
    return first >= second;
  }
  public static int f2(int[] nums, int l, int r, int[][] dp) {
    if (dp[l][r] != -1) {
      return dp[l][r];
    }
    int ans;
    if (l == r) {
      ans = nums[l];
    } else if (l == r - 1) {
      ans = Math.max(nums[l], nums[r]);
    } else {
      int p1 = nums[l] + Math.min(f2(nums, l + 2, r, dp), f2(nums, l + 1, r - 1, dp));
      int p2 = nums[r] + Math.min(f2(nums, l + 1, r - 1, dp), f2(nums, l, r - 2, dp));
      ans = Math.max(p1, p2);
    }
    dp[l][r] = ans;
    return ans;
  }
  // 严格位置依赖的动态规划
  public static boolean predictTheWinner3(int[] nums) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    int n = nums.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n - 1; i++) {
      dp[i][i] = nums[i];
      dp[i][i + 1] = Math.max(nums[i], nums[i + 1]);
    }
    dp[n - 1][n - 1] = nums[n - 1];
    for (int l = n - 3; l >= 0; l--) {
      for (int r = l + 2; r < n; r++) {
        dp[l][r] = Math.max(
            nums[l] + Math.min(dp[l + 2][r], dp[l + 1][r - 1]),
            nums[r] + Math.min(dp[l + 1][r - 1], dp[l][r - 2]));
      }
    }
    int first = dp[0][n - 1];
    int second = sum - first;
    return first >= second;
  }
}

package class076;
// 多边形三角剖分的最低得分
// 你有一个凸的 n 边形，其每个顶点都有一个整数值
// 给定一个整数数组values，其中values[i]是第i个顶点的值(顺时针顺序)
// 假设将多边形 剖分 为 n - 2 个三角形
// 对于每个三角形，该三角形的值是顶点标记的乘积
// 三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和
// 返回 多边形进行三角剖分后可以得到的最低分
// 测试链接 : https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/
public class Code03_MinimumScoreTriangulationOfPolygon {
  // 记忆化搜索
  public static int minScoreTriangulation1(int[] arr) {
    int n = arr.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dp[i][j] = -1;
      }
    }
    return f(arr, 0, n - 1, dp);
  }
  public static int f(int[] arr, int l, int r, int[][] dp) {
    if (dp[l][r] != -1) {
      return dp[l][r];
    }
    int ans = Integer.MAX_VALUE;
    if (l == r || l == r - 1) {
      ans = 0;
    } else {
      // l....r >=3
      // 0..1..2..3..4...5
      for (int m = l + 1; m < r; m++) {
        // l m r
        ans = Math.min(ans, f(arr, l, m, dp) + f(arr, m, r, dp) + arr[l] * arr[m] * arr[r]);
      }
    }
    dp[l][r] = ans;
    return ans;
  }
  // 严格位置依赖的动态规划
  public static int minScoreTriangulation2(int[] arr) {
    int n = arr.length;
    int[][] dp = new int[n][n];
    for (int l = n - 3; l >= 0; l--) {
      for (int r = l + 2; r < n; r++) {
        dp[l][r] = Integer.MAX_VALUE;
        for (int m = l + 1; m < r; m++) {
          dp[l][r] = Math.min(dp[l][r], dp[l][m] + dp[m][r] + arr[l] * arr[m] * arr[r]);
        }
      }
    }
    return dp[0][n - 1];
  }
}

package class076;
import java.util.Arrays;
// 切棍子的最小成本
// 有一根长度为n个单位的木棍，棍上从0到n标记了若干位置
// 给你一个整数数组cuts，其中cuts[i]表示你需要将棍子切开的位置
// 你可以按顺序完成切割，也可以根据需要更改切割的顺序
// 每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和
// 对棍子进行切割将会把一根木棍分成两根较小的木棍
// 这两根木棍的长度和就是切割前木棍的长度
// 返回切棍子的最小总成本
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/
public class Code04_MinimumCostToCutAStick {
  // 记忆化搜索
  public static int minCost1(int n, int[] cuts) {
    int m = cuts.length;
    Arrays.sort(cuts);
    int[] arr = new int[m + 2];
    arr[0] = 0;
    for (int i = 1; i <= m; ++i) {
      arr[i] = cuts[i - 1];
    }
    arr[m + 1] = n;
    int[][] dp = new int[m + 2][m + 2];
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= m; j++) {
        dp[i][j] = -1;
      }
    }
    return f(arr, 1, m, dp);
  }
  // 切点[l....r]，决定一个顺序
  // 让切点都切完，总代价最小
  public static int f(int[] arr, int l, int r, int[][] dp) {
    if (l > r) {
      return 0;
    }
    if (l == r) {
      return arr[r + 1] - arr[l - 1];
    }
    if (dp[l][r] != -1) {
      return dp[l][r];
    }
    int ans = Integer.MAX_VALUE;
    for (int k = l; k <= r; k++) {
      ans = Math.min(ans, f(arr, l, k - 1, dp) + f(arr, k + 1, r, dp));
    }
    ans += arr[r + 1] - arr[l - 1];
    dp[l][r] = ans;
    return ans;
  }
  // 严格位置依赖的动态规划
  public static int minCost2(int n, int[] cuts) {
    int m = cuts.length;
    Arrays.sort(cuts);
    int[] arr = new int[m + 2];
    arr[0] = 0;
    for (int i = 1; i <= m; ++i) {
      arr[i] = cuts[i - 1];
    }
    arr[m + 1] = n;
    int[][] dp = new int[m + 2][m + 2];
    for (int i = 1; i <= m; i++) {
      dp[i][i] = arr[i + 1] - arr[i - 1];
    }
    for (int l = m - 1, next; l >= 1; l--) {
      for (int r = l + 1; r <= m; r++) {
        next = Integer.MAX_VALUE;
        for (int k = l; k <= r; k++) {
          next = Math.min(next, dp[l][k - 1] + dp[k + 1][r]);
        }
        dp[l][r] = arr[r + 1] - arr[l - 1] + next;
      }
    }
    return dp[1][m];
  }
}

package class076;
// 戳气球
// 有 n 个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中
// 现在要求你戳破所有的气球。戳破第 i 个气球
// 你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币
// 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号
// 如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球
// 求所能获得硬币的最大数量
// 测试链接 : https://leetcode.cn/problems/burst-balloons/
public class Code05_BurstBalloons {
  // 记忆化搜索
  public static int maxCoins1(int[] nums) {
    int n = nums.length;
    // a b c d e
    // 1 a b c d e 1
    int[] arr = new int[n + 2];
    arr[0] = 1;
    arr[n + 1] = 1;
    for (int i = 0; i < n; i++) {
      arr[i + 1] = nums[i];
    }
    int[][] dp = new int[n + 2][n + 2];
    for (int i = 1; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        dp[i][j] = -1;
      }
    }
    return f(arr, 1, n, dp);
  }
  // arr[l...r]这些气球决定一个顺序，获得最大得分返回！
  // 一定有 : arr[l-1]一定没爆！
  // 一定有 : arr[r+1]一定没爆！
  // 尝试每个气球最后打爆
  public static int f(int[] arr, int l, int r, int[][] dp) {
    if (dp[l][r] != -1) {
      return dp[l][r];
    }
    int ans;
    if (l == r) {
      ans = arr[l - 1] * arr[l] * arr[r + 1];
    } else {
      // l   ....r
      // l +1 +2 .. r
      ans = Math.max(
          arr[l - 1] * arr[l] * arr[r + 1] + f(arr, l + 1, r, dp), // l位置的气球最后打爆
          arr[l - 1] * arr[r] * arr[r + 1] + f(arr, l, r - 1, dp));// r位置的气球最后打爆
      for (int k = l + 1; k < r; k++) {
        // k位置的气球最后打爆
        // l...k-1  k  k+1...r
        ans = Math.max(ans, arr[l - 1] * arr[k] * arr[r + 1] + f(arr, l, k - 1, dp) + f(arr, k + 1, r, dp));
      }
    }
    dp[l][r] = ans;
    return ans;
  }
  // 严格位置依赖的动态规划
  public static int maxCoins2(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = 1;
    arr[n + 1] = 1;
    for (int i = 0; i < n; i++) {
      arr[i + 1] = nums[i];
    }
    int[][] dp = new int[n + 2][n + 2];
    for (int i = 1; i <= n; i++) {
      dp[i][i] = arr[i - 1] * arr[i] * arr[i + 1];
    }
    for (int l = n, ans; l >= 1; l--) {
      for (int r = l + 1; r <= n; r++) {
        ans = Math.max(arr[l - 1] * arr[l] * arr[r + 1] + dp[l + 1][r],
            arr[l - 1] * arr[r] * arr[r + 1] + dp[l][r - 1]);
        for (int k = l + 1; k < r; k++) {
          ans = Math.max(ans, arr[l - 1] * arr[k] * arr[r + 1] + dp[l][k - 1] + dp[k + 1][r]);
        }
        dp[l][r] = ans;
      }
    }
    return dp[1][n];
  }
}

package class076;
// 布尔运算
// 给定一个布尔表达式和一个期望的布尔结果 result
// 布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成
// 布尔表达式一定是正确的，不需要检查有效性
// 但是其中没有任何括号来表示优先级
// 你可以随意添加括号来改变逻辑优先级
// 目的是让表达式能够最终得出result的结果
// 返回最终得出result有多少种不同的逻辑计算顺序
// 测试链接 : https://leetcode.cn/problems/boolean-evaluation-lcci/
public class Code06_BooleanEvaluation {
  // 记忆化搜索
  public static int countEval(String str, int result) {
    char[] s = str.toCharArray();
    int n = s.length;
    int[][][] dp = new int[n][n][];
    int[] ft = f(s, 0, n - 1, dp);
    return ft[result];
  }
  // s[l...r]是表达式的一部分，且一定符合范式
  // 0/1  逻  0/1   逻       0/1
  //  l  l+1  l+2  l+3........r
  // s[l...r]  0 : ?
  //           1 : ?
  // ans : int[2] ans[0] = false方法数 ans[0] = true方法数
  public static int[] f(char[] s, int l, int r, int[][][] dp) {
    if (dp[l][r] != null) {
      return dp[l][r];
    }
    int f = 0;
    int t = 0;
    if (l == r) {
      // 只剩一个字符，0/1
      f = s[l] == '0' ? 1 : 0;
      t = s[l] == '1' ? 1 : 0;
    } else {
      int[] tmp;
      for (int k = l + 1, a, b, c, d; k < r; k += 2) {
        // l ... r
        // 枚举每一个逻辑符号最后执行 k = l+1 ... r-1  k+=2
        tmp = f(s, l, k - 1, dp);
        a = tmp[0];
        b = tmp[1];
        tmp = f(s, k + 1, r, dp);
        c = tmp[0];
        d = tmp[1];
        if (s[k] == '&') {
          f += a * c + a * d + b * c;
          t += b * d;
        } else if (s[k] == '|') {
          f += a * c;
          t += a * d + b * c + b * d;
        } else {
          f += a * c + b * d;
          t += a * d + b * c;
        }
      }
    }
    int[] ft = new int[] { f, t };
    dp[l][r] = ft;
    return ft;
  }
}