首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode实战:动态规划算法是怎么一回事

LeetCode实战:动态规划算法是怎么一回事

作者头像
double
发布2018-04-02 13:19:27
9830
发布2018-04-02 13:19:27
举报
文章被收录于专栏:算法channel算法channel

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。

0

回顾

利用了6天时间,细细总结了8个常用排序算法的原理到源码兑现,如果您对排序算法感兴趣或者想了解这些算法用到的思想,比如分治法,递归调用,堆排序等,然后尽量学着将这些思想用到工作的coding中去,请参考之前推送:

冒泡排序到快速排序做的那些优化

直接选择排序到堆排序做的那些改进

直接插入排序到希尔排序做的那些改进

归并排序算法的过程图解

不基于比较的基数排序原理图解

常用排序算法代码兑现

01

你会学到什么?

接下来,要学习一种算法优化的思路。

暴力枚举,一般比较容易想出来,是解决问题最直接的方法,但是往往不是高效的算法,找出暴力枚举的问题所在,以此为突破口,才有可能想出更高效的算法。

这种更高效的算法有可能是动态规划。看看如何通过实战从暴力枚举切入到动态规划中。

02

讨论的问题是什么?

已知目标函数,和多个输入变量,并且输入变量间有耦合关系,对于这类问题,暴力解决一般时间复杂度比较大,讨论动态规划来降低时间复杂度。

03

动态规划入门

先考虑这么一个问题,给定两个数组a和 b,每个数组任意拿出一个元素,求乘积的最大值,假定数组 a 和 b 相互独立,不存在耦合关系。

在这个假定下,这个问题变得就很简单了,直接取各自数组a或b的最大值,两者相乘一定是最大值。

但是,有时候,数组a和b不会相互独立,存在耦合关系,例如数组a中最大元素取出后,就不能再拿数组b中的最大值了,此时问题就好像变得复杂起来了啊。

这就是我们说的需要规划,需要有策略的动态地调整数组a和b拿出的元素,最后的相乘最大值,可能都不是各自的最大元素。

上述问题,转化为一个实际问题,便是LeetCode的第11题 container with most water,请看题,

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and n is at least 2.

题目的意思是求索引 i j 的距离乘以两者对应高度的较小值,取这个目标函数的最大值。

04

解决问题的方法

提取出这个问题的模型,如下所示,

目标函数: Max{(j-i) * Min( h(i), h(j) )}, 约束条件: i < j, i >= 0 , j <= n-1 .

分析。我们假定面积的最大值为 (n-1) 乘以h(0)和h(n-1)的较小高度,即

max_area = (n-1) * Min( h(0), h(n-1))

那么这个假设一定成立吗?

显然不一定,(n-1)一定是最大值,但是 Min( h(0), h(n-1)) 未必是最大值,所以两者的乘积不一定是最大值。

看看两个数的乘积,10 * 3, 8 * 5, 5 * 6, 3 * 2,可以看到间隔虽然变小了,但是较小的高度可能变大了,最大值为 8 * 5 = 40 。

那么,我们该朝着哪个方向去寻找可能的面积最大值呢?

暴力枚举

采用暴力解法,每个高度与剩余的高度比较大小,取小者然后乘以x轴的对应距离,这样会得到 n*(n-1)/2个面积,取最大的面积,这样下来算法的时间复杂度为 O(n^2)。

暴力解法当然不是好的算法,那么问题是暴力枚举算法低效的原因是什么? 只有找出原因,才可能优化我们的问题。

为了解开这个答案,我们还得从目标函数下手,分析出哪些枚举是没有任何价值的。为了方便说明问题,请看下图,

从图中可以看出,如果我们选择了索引1,即 i = 1, height(1) = 2,此时的目标函数变为,

Max{(j-1) * Min( h(1), h(j) )},

其中 j = 2,3,..., 7

在暴力枚举中,分别求其他索引对应的高度,即分别求出 h(j) ,其中 j = 2~7,然后得到 6个 (j-i) * Min(hj, hi),取最大的那个,这样完成一趟枚举。

这种方法总结起来就是每趟锁定 i,不断调整 j,然后更新最大面积值。但是想想看,

  1. 如果 h(7) >= h(1),我们还有必要再遍历h(6),h(5),...,h(2)吗,其实不用,这便是暴力算法的冗余之处,多做了很多次无用的遍历,i = 1这趟遍历中,最大面积一定为 (7-1) * h(1) ;
  2. 如果 h(7) < h(1),我们再尝试h(6),如果h(6)>=h(1),那么在i = 1这趟遍历中的面积最大为(6-1) * h(1),没必要再试h(5)了,依次这样下去。

动态规划

面积初始值令 j - i 最大,即取最大间隔,然后动态地交替地调整 i, 和 j 的取值,这样尽可能地每次试着增大 Min( h(i), h(j)) 值。只有这样,我们才有可能取到更大的面积值。

算法思路

  1. 面积最大值初始值设定 maxarea;
  2. i, j 分别指向索引两头,动态交替地调整 i, j ,进而尝试取得较大的相对高度,这个调整的策略是关键,同时,更新目标函数即面积的最大值,如果大于maxarea,则更新;
  3. 直到 i >= j 为止;
  4. 返回最大值。

public int maxArea(int[] height) { int i = 0; int j = height.length - 1; int maxarea = (j-i) * Math.min(height[i],height[j]); while(i<j){ int updatearea = (j-i)* Math.min(height[i],height[j]); maxarea = Math.max(maxarea, updatearea); if(height[i]<height[j]) i++; else j--; } return maxarea; }

以上算法的动画演示如下,(这个算法的最后一帧没有放入到动画中)。可以看到 i, j 的值动态得地交替地调整,直至碰头。

05

算法评价

动态规划后的算法时间复杂度为 O(n),空间复杂度为 O(1) 。

显然时间性能比暴力算法相比提高了。

06

总结

暴力枚举做了很多次冗余的遍历,要想消除这些冗余,需要结合目标函数,本算法借助动态规划思想,使问题的解快速收敛。

动态规划算法是从目标函数入手,分析影响目标函数的几个变量,朝着优化的方向,调整这几个变量,然后重新计算目标函数的值,最终获得最佳优化解。

以上分析,全部手写码字,术语未必是标准计算机科学术语,但是保证容易让人理解。

最后,看下动态规划思想在百度中的阐述,

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。 我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

07

GitChat

这是我发起的一次Chat,诚邀您的参与!

最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

越到最后,你越会明白算法和数据结构很 cool,很 essential。这些都是内功,和用什么语言、技术或框架无关。本场 Chat 的主要内容包括:

  • 8 个主要排序算法的思想和原理图解,代码兑现
  • 从冒泡排序到快速排序做的那些优化
  • 从直接选择排序到堆排序做的那些改进
  • 从直接插入排序到希尔排序做的那些改进
  • 归并排序算法的过程图解
  • 不基于比较的基数排序原理图解
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-11-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员郭震zhenguo 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 这是我发起的一次Chat,诚邀您的参与!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档