区间DP

375. 猜数字大小 II

难度中等274收藏分享切换为英文接收动态反馈
我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
示例:
n = 10, 我选择了8.

第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。

给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

分析：
以 i为第一次尝试找到最小开销的过程可以被分解为找左右区间内最小开销的子问题。对于每个区间，我们重复问题拆分的过程，得到更多子问题，这启发我们可以用 DP 解决这个问题。

我们需要使用一个 dpdp 矩阵，其中 dp(i, j)dp(i,j) 代表在 (i, j)(i,j) 中最坏情况下最小开销的代价。现在我们只需要考虑如何求出这个 dpdp 数组。如果区间只剩下一个数 kk ，那么猜中的代价永远为 0 ，因为我们区间里只剩下一个数字，也就是说，所有的 dp(k, k)dp(k,k) 都初始化为 0 。然后，对于长度为 2 的区间，我们需要所有长度为 1 的区间的结果。由此我们可以看出，为了求出长度为 lenlen 区间的解，我们需要所有长度为 len-1len−1 的解。因此我们按照区间长度从短到长求出 dpdp 数组。

现在，我们应该按照什么办法来求出 dpdp 矩阵呢？对于每个 dp(i, j)dp(i,j) ，当前长度为 len=j-i+1len=j−i+1 。我们遵照方法 1 中俄办法，依次挑选每个数字作为第一次尝试的答案，可以求出最小开销：

但是在计算开销的时候我们有一个便利之处，就是我们已经知道了小于 lenlen 长度 dpdp 数组的所有答案。因此 dp 方程式变成了：

其中 表示将 (i, j)(i,j) 中的每个数作为第一个尝试的数。

下面的动画更好地说明了 n=5 的情况：

作者：LeetCode
链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/solution/cai-shu-zi-da-xiao-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * @param {number} n
 * @return {number}
 */
var getMoneyAmount = function(n) {
  const dp = new Array(n + 1);
  for (let i = 0; i < n + 1; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }
  for (let len = 2; len <= n; len++) {
    for (let start = 1; start <= n - len + 1; start++) {
      let minres = Number.MAX_VALUE;
      // 寻找满足最小值的分界点，
      for (let piv = start + ((len - 1) >>> 1); piv < start + len - 1; piv++) {
        let res = piv + Math.max(
          dp[start][piv - 1], 
          dp[piv + 1][start + len - 1]
        );
        minres = Math.min(res, minres);
      }
      dp[start][start + len - 1] = minres;
    }
  }
  return dp[1][n];
};

复杂度分析

时间复杂度： O(n^3) 。我们遍历 dpdp 数组一遍需要 O(n^2) ) 的时间开销。对于数组中每个元素，我们最多需要遍历 nn 个数字。

空间复杂度： O(n^2)。需要创建 n^2 空间的 dpdp数组。

优化的 DP
算法

在上一个方法中，我们尝试使用 (i, j)(i,j) 中的每一个数作为第一个选的数。但由于方法 2 中提到的原因，我们只需要从 \big(i+(len-1)/2,j\big)(i+(len−1)/2,j) 中选第一个数就可以了，其中 lenlen 是当前区间的长度。因此转移方程式为：

通过这种方法我们可以在一定程度上优化方法 3 。

public class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int minres = Integer.MAX_VALUE;
                for (int piv = start + (len - 1) / 2; piv < start + len - 1; piv++) {
                    int res = piv + Math.max(dp[start][piv - 1], dp[piv + 1][start + len - 1]);
                    minres = Math.min(res, minres);
                }
                dp[start][start + len - 1] = minres;
            }
        }
        return dp[1][n];
    }
}

复杂度分析

时间复杂度： O(n^3) 。我们遍历整个 dp 矩阵一次需要 O(n^2)的时间。对于数组中每个元素，我们最多需要遍历 个元素。

空间复杂度： O(n^2) 。 dpdp 数组的空间开销为 n^2 。

53. 最大子序和

难度简单3642收藏分享切换为英文接收动态反馈
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [0] 输出：0
示例 4：
输入：nums = [-1] 输出：-1
示例 5：
输入：nums = [-100000] 输出：-100000

提示：

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  // const dp = new Array(nums.length).fill(0);
  let ans = nums[0];
  let max = ans;
  for (let i = 1; i < nums.length; i++) {
    ans = Math.max(ans + nums[i], nums[i]);
    max = Math.max(max, ans);
  }
  return max;
};