[一篇看懂] 最优化问题: 分治法贪心算法动态规划(举例说明)_综合

欢迎指教欢迎评论留言

分治算法

先划分, 大问题变小问题,
等到问题规模小到可以直接解决了,再去处理这个足够小的子问题
最后将子问题的最优解’合并’起来, 组合成原问题的最终解.
三种解决方案都是将大规模的难解的问题改成小规模容易解的问题.
比如分治算法经典的’最大子序和’问题.

举例:53. 最大子序和

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

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

分治算法解分析

class Solution {
    public int maxSubArray(int[] nums) {
    // 最优子串可能在左串 可能在右串 可能是包含中间元素的中间串return recur(nums,0,nums.length-1);}// 递归 分治法private int recur(int[] nums, int l, int r) {
    if(l==r) return nums[l];// 只有一个元素的时候int mid=(l+r)/2;// 对左中右取最大 int leftSum=recur(nums,l,mid);int rightSum=recur(nums,mid+1,r);// cross的计算不是原问题规模更小的问题 是合并的一部分int crossSum=midSum(nums, l, r, mid);int res=Math.max(leftSum, Math.max(rightSum, crossSum));return res;}// 求中间子串: 这个求和不是原问题的子问题(必须 跨越中点) 所以不用recur()计算private int midSum(int[] nums, int l, int r,int mid) {
    if(l==r) return nums[l];// 只有一个元素int sumTmp=0,leftSum=Integer.MIN_VALUE;int rightSum=leftSum;for(int i=mid;i!=-1;i--) {
    sumTmp+=nums[i];leftSum=Math.max(sumTmp, leftSum);}// 包括mid位置的左半边最大和sumTmp=0;for(int i=mid+1;i!=nums.length;i++) {
    sumTmp+=nums[i];rightSum=Math.max(sumTmp, rightSum);}// 不包括mid位置的右半边最大和return leftSum+rightSum;}
}

分析原问题,发现问题的解无外乎三中情况. 子序列都在在mid的前面, 或子序列都在mid的后面, 或子序列不都在前面也不都在后面, 跨越了mid, 前后都有的, 代码中的midSum函数就是算这个的.
原问题划分为:

1.前半部分和 2. 后半部分和 3. 包括中间的中间部分和.

前后半部分都是大问题变小问题经典的形式, 中间部分和不是原问题的同结构子问题, 所以是属于分治算法的合并部分

动态规划算法

三种解决方案都需要’最优子结构’形式,
分治的最优子问题互相独立, 没有’重叠子问题’的情况; 如果有这个问题,直接使用分治算法会有许多的子问题需要重复计算. 用动态规划可以大大的减少时间花销.
动态规划有自顶向下和自底向上两种方法:
- 自顶向下方法其实就是带备忘录的分治算法, 在每次递归调用时, 将结果存在一个’备忘录’中, 它可以是一个数组. 在需要子问题解的时候不需要再次计算子问题的解, 直接返回先前已经计算的结果(如果没有计算过的话就继续计算)
- 自底向上的方法其实是从小规模问题到大规模问题, 计算较大规模最优解是会利用到刚刚(上回循环)计算出的较小规模最优解的结果, 每个子问题只会计算一次, 大大减少时间复杂度.自底向上说到底就是在大问题可以化成小问题的基础想, 从小问题出发, 逐渐扩大, 最终扩大到原本问题的规模

举例: 55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

动态规划算法分析

回溯法

public class Solution {
    public boolean canJumpFromPosition(int position, int[] nums) {
    if (position == nums.length - 1)  return true;int furthestJump = Math.min(position + nums[position], nums.length - 1);// 避免跳到超出数据容量处去了for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) // 从position+1处开始找能跳的点if (canJumpFromPosition(nextPosition, nums))return true;return false;}public boolean canJump(int[] nums) {
    // 从0开始遍历递归return canJumpFromPosition(0, nums);}
}

时间复杂度是O(2^n), 幂级的时间复杂度, 很明显需要优化
原问题有’最优子结构’, 的确是不断缩小范围. 并且在递归的过程中有很多重复的子问题的计算
- 对于重复子问题往往使用动态规划可以优化时间复杂度
并且发现这种分治每次缩小范围都是只剩下一个子问题, 说不定可以使用贪心算法(下文会说)

自顶向下(用空间换时间)

enum Index {
     // 设计了一个每局变量GOOD, BAD, UNKNOWN 
}
public class Solution {
    Index[] memo;// 判断每一个位置能不能跳到尾巴(end)public boolean canJump(int[] nums) {
    memo = new Index[nums.length];for (int i = 0; i < memo.length; i++) memo[i] = Index.UNKNOWN;// 初始化memo数组memo[memo.length - 1] = Index.GOOD;// 最尾巴位置可以跳return canJumpFromPosition(0, nums);}private boolean canJumpFromPosition(int position, int[] nums) {
    // 以下两行就是动态规划自顶向下的精髓(也叫带备忘录的动态规划)if (memo[position] != Index.UNKNOWN) // 若当前位置可以跳 直接返回return memo[position] == Index.GOOD ? true : false;//若对应的子问题没有求解过, 则继续计算int furthestJump = Math.min(position + nums[position], nums.length - 1);// 避免跳到超出数据容量处去了for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
    // 从position+1处开始找能跳的点if (canJumpFromPosition(nextPosition, nums)) {
    memo[position] = Index.GOOD;return true;}}// 找不到能跳的点memo[position] = Index.BAD;return false;}

自底向上

	public boolean canJump2(int[] nums) {
    // can数组标识当前位置是否能跳到尾巴(end)boolean[] can=new boolean[nums.length];// 默认为falsecan[nums.length-1]=true;// 最尾为真(可跳)int jumpMax=0;//最远可跳的距离for(int i=nums.length-2;i>=0;i--) {
    //从len-2向前遍历//i+nums[i]是i处可跳的距离jumpMax=Math.min(i+nums[i], nums.length-1);for(int j=i+1;j<=jumpMax;j++)//从i+1遍历到jumpMax 看有没有可达尾的if(can[j]) can[i]=true; break;}return can[0];}

贪心算法

贪心算法通常是自顶向下的算法, 每一步贪心都把当前问题的规模缩减一点
贪心算法在使用时要证明(相当于做了数学归纳法):

证明做出当前的贪心选择后**, 只剩下一个子问题**, 不能像分治和动态一样有多个子问题.
证明贪心选择总是安全的, 能够一路贪心贪到原问题最优解

贪心算法实际是对每一步的当前问题找最优解, 不依赖于子问题的最优解和将来选择的最优解

优化
如果在贪心算法的每步操作时, 不得不考虑众多选择: 很多时候需要对原问题的输入输入做点排序操作. 便于每步贪心时减少’查找当前问题最优解’的时间复杂度.

举例: 跳跃游戏

public boolean canJump(int[] nums) {
    int leftMostIndex=nums.length-1;// 初始化为最右元素for(int i=nums.length-1;i>=0;i--) {
    // 从后往前//每次遍历贪到最右(最大下标)if(nums[i]+i>=leftMostIndex)//i处的元素够得到 '最左可达元素'leftMostIndex=i;}return leftMostIndex==0;}

每步贪心的确是可以缩减规模, 并只剩下左部分规模的子问题
每步都贪’最左’的元素, 如果最左元素都够不到的话, 就是不可达, 如果最左元素够得到, 那就是可达

举例2: 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
    int len = nums.length;int currSum = nums[0]; // 每一步的当前最优解int maxSum = nums[0];// 从左到右 每步贪心for (int i = 1; i < len; ++i) {
    // 每步都贪出当前 以j结尾的最大值;currSum = Math.max(nums[i], currSum + nums[i]);// 更新maxSummaxSum = Math.max(maxSum, currSum);}return maxSum;}
}

currSum = Math.max(nums[j], currSum + nums[j]);
- 比较以j结尾的某个’最大子数组和’和[j]的值
- 若[i,j]的值更大或二者相等
  - '最大子数组’加一个元素
  - currSum更新为[i,j]的大小
- 若[i,j]的值比[j]的值小
  - 还不如从j开始新的’最大连续子数组’
  - 更新’currSum’
- 若最大子数组不是以[j-1]结尾的
  - 其对应的值早就存在maxSum中,是currSum的曾经的某一个赋值
  - maxSum = Math.max(maxSum, currSum);比较时也不会影响maxSum的正确性

贪心算法常见解决问题

单源最短路径问题, 最小生成树问题

[一篇看懂] 最优化问题: 分治法 贪心算法 动态规划(举例说明)