算法神器——动态规划

title: 算法神器——动态规划 id: a101819e28e80118446b9280226e4ae0 tags: [] date: 2000/01/01 00:00:00 updated: 2023/03/04 19:29:12 isPublic: true --#|[分隔]|#--

算法神器——动态规划

动态规划在处理某类问题时，具有性能和处理速度上极佳的处理能力。

这类问题需要处理一个数组，需要在数组中找到某几项的组合，使满足最佳条件，之前的决策会影响之后的决策。

动态规划一般解题思路，是遍历数组，遍历到每一项，都取一下之前的最优解，再计算一下当前项参与时的最优解，从两个最优解中更优的，存起来继续遍历。

数组中连续几项的和的最大的值

问题： 给定只包含正负整数的数组，获取数组中连续几项的和，最大的值是多少。

思路：

如果使用暴力解，那就需要使用双重 for 循环，很消耗性能。

使用动态规划，就代码比较简单，但理解上需要费一些脑细胞。

遍历数组，遍历到某一项时，得到把前项作为新的「连续几项」的第一项时，取他们的和（其实就是当前项的值）为A，再计算把当前项为「连续几项」的最后一项时，他们的和为B，对比A和B，只保留大的那个值。

然后，再有一个变量，用来保留遍历历史上，出现过的和的最大值，当把整个数组遍历完，这个变量就是最终的产出。

解题：

声明两个变量：

• accumulate：累积值，当遍历数组时，用它来保存以当前项为「连续几项」的最后一项时，和的最大值。

• maxValue：保留整体最大值，因为 accumulate 需要每次遍历时计算。

// 给定只包含正负整数的数组，获取数组中连续几项的和，最大的值是多少
let maxSubArray = function(nums) {
  let accumulate = nums[0] // 累积值
  let maxValue = nums[0] // 整体最大值

  for (let i = 1; i < nums.length; i ++ ) {

    // 对比「当前项」 和 「累积值 + 当前项」，取两者中比较大的那个结果，赋值给新的「累积值」
    // 因为前几项的和可能是负值，而当前项是正值，此时就该舍弃前几项
    // 把当前项作为「连续几项」唯一的一项
    accumulate = Math.max(nums[i], accumulate + nums[i])

    // 对比「整体最大值」 和 「累积值」，取两者中比较大的那个结果，赋值给新的「整体最大值」
    // 参考 accumulate 的定义，有可能旧的 accumulate 值是正数，而 nums[i] 是负值
    // 那么 nums[i] 和 accumulate + nums[i]，他们的值都比 accumulate 小
    // maxValue 就用来保存，遍历历史上，出现过的那个最大的和
    maxValue = Math.max(maxValue, accumulate)
  }

  return maxValue
}

买入卖出股票获利最大

问题：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票，设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润，如果你不能获取任何利润，返回 0 。

思路：

暴力解同样上一个问题，需要双重for循环。

动态规划：遍历数组，遍历前设两个变量：

• sellToday：今天卖出，手中剩余的钱，默认值为0。

• buyToday：今天买入，将要花费的钱，默认认为第一天买入，值为prices[0]。

然后遍历数组，分别判断留值，最终的 sellToday 为最终结果。

解题：

let maxSubArray = function(prices) {
  let sellToday = 0 // 今天卖出，手中剩余的钱(默认为0)
  let buyToday = prices[0] // 今天买入，将要花费的钱(默认在第一天买入了)

  for (let i = 1; i < prices.length; i++) {
    // 对比「今天卖出」和「之前已经卖出」，取获利最大的值，保留
    sellToday = Math.max(prices[i] - buyToday, sellToday)
    // 对比「今天买入」和「之前已经买入」，取花费更少的值，保留
    buyToday = Math.min(prices[i], buyToday)
  }
  return sellToday
}

数组中连续几项的乘积的最大的值

问题：

给定只包含正负整数的数组，获取数组中连续几项的乘积，最大的值是多少。

看似和「连续几项的和」的那道题类似，但是，数组中可能会出现负数，一个负数的出现，可能会把一个最小值变成最大值。

思路：

遍历数组时，需要把每次遍历时，正数的最大值和负数的最小值都记录一下，以便应对后面可能发生的正负转换。

解题一：

var maxProduct = function(nums) {
  
  let upMax = 0 // 正数时的最大值
  let downMin = 0 // 负数时的最小值
  let max = 0 // 历史中出现过的最大值

  for (let i = 0; i < nums.length; i++) {
    // 把上一次的两个值先存一下，
    let _upMax = upMax, _downMin = downMin

    if (nums[i] > 0) {
      // 当前项是正值
      upMax = Math.max(nums[i], (_upMax || 1) * nums[i])
      downMin = _downMin ? _downMin * nums[i] : 0
    } else if (nums[i] < 0) {
      // 当前项是负值
      upMax = _downMin ? _downMin * nums[i] : 0
      downMin = Math.min(nums[i], (_upMax || 1) * nums[i])
    } else {
      // 当前项是 0
      upMax = 0
      downMin = 0
    }

    max = Math.max(max, upMax)
  }

  return max
}

解题二：

上面的题解代码相对更多，下面这个题解的思路是一样的，但是代码精简了：

var maxProduct = function(nums) {
  let max = nums[0]; // 最大值
  let min = nums[0]; // 最小值
  let res = nums[0]; // 历史中的最大值

  for (let i = 1; i < nums.length; i++) {
    let tmp = min; // 暂存一下上一次的最小值
    min = Math.min(nums[i], Math.min(max * nums[i], min * nums[i])); // 取最小
    max = Math.max(nums[i], Math.max(max * nums[i], tmp * nums[i])); /// 取最大
    res = Math.max(res, max);
  }
  return res;
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

解题：

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  let last = nums[0] || 0 // 本次偷了
  let notLast = 0 // 本次没偷

  for (let i = 1; i < nums.length; i++) {
    let last_pre = last;
    last = notLast + nums[i]
    notLast = Math.max(notLast, last_pre)
  }
  return Math.max(last, notLast)
};