老九的程序进阶之路

动态优化

概念

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

与分治算法相比

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

  • 最优化原理（最优子结构性质）一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

  • 无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

  • 子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

分类

  • 线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
  • 区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
  • 树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
  • 背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等

应用案例

案例大多从leetCode和其他网络文章收集

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

这是一道明显的最优子结构的动态规划的算法题，首先符合上述动态优化的特性，那么我们开始明确动态优化的步骤：

  1. 分阶段
    我们可以把数组分为3个阶段，最优子结构之前、最优子结构、最优子结构之后；当然也可能是两个阶段，道理相同；描述阶段的变量称为阶段变量。我们把每个阶段的序列和称为阶段变量。
    如例子，[-2,1,-3]就是最优子结构之前的阶段；[-5,4]是最优子结构之后的阶段。

  2. 明确状态
    每个阶段都会有两个状态，一个是当前阶段起始位置之前，也是上一个阶段的终止位置；另一个是当前阶段的终止位置，也是下一个阶段的起始位置。我们把这个终止状态看成是一个阶段变量，也就是子序列之和。

  3. 找到最优策略
    根据上面的状态，我们需要用两个变量来保存，我们用startSum表示上一阶段的阶段变量，用endSum来表示最优策略；所以当前阶段的最优解就是endSum=Math.max(sum[i],startSum+sum[i])。sum[i]表示当前阶段的阶段变量。
    以每个位置为终点的最大子数列和 都是基于其前一位置的最大子数列和计算得出。

  4. 明确状态转移方程
    状态转移方程：sum[i] = max{sum[i-1]+a[i],a[i]}

/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
    
  if (!nums.length) {
        return;
    };
    // 以数组第一个数字为第一个阶段，他的起始阶段和终止阶段都是本身
    let startSum = nums[0];
    let endSum = nums[0];

    for (let i = 1; i < nums.length; i ++ ) {
        //当前阶段的最优策略是当前阶段的阶段变量和上一阶段的阶段变量相比取的最大值
      startSum = Math.max (startSum + nums[i], nums[i] );
      endSum = Math.max ( startSum, endSum);
  };
    };

    return endSum;
  
};

继续优化

//我们可以把 startSum = Math.max (startSum + nums[i], nums[i] )
//写成if(startSum + nums[i] > nums[i] ){startSum = startSum + nums[i];} 
var maxSubArray = function(nums) {
    
  let endSum = nums[0];
  let startSum = 0;
  for(let num of nums) {
      // if(startSum + num > num) { 可以写成这样
      if(startSum > 0 ){
          startSum = startSum + num;
      } else {
          startSum = num;
      }
      endSum = Math.max(startSum, endSum);
  };
  return endSum;
};

← 分治算法 →