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

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

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 个主要排序算法的思想和原理图解,代码兑现
  • 从冒泡排序到快速排序做的那些优化
  • 从直接选择排序到堆排序做的那些改进
  • 从直接插入排序到希尔排序做的那些改进
  • 归并排序算法的过程图解
  • 不基于比较的基数排序原理图解

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-11-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木可大大

算法初体验

在介绍具体算法之前,我先谈一下个人对学习算法的初心。我的初心无非有两点:一,BAT等互联网公司招聘面试时要问算法知识,如果想要进入互联网公司,我就必须学好算法;...

4779
来自专栏机器之心

入门 | 一文介绍机器学习中基本的数学符号

选自Machine Learning Mastery 作者:Jason Brownlee 机器之心编译 参与:Edison Ke、黄小天 本文介绍了机器学习中的...

3639
来自专栏后端技术探索

两道腾讯技术面试题(二面经历)

假设给定一个由字母和小数点组成的字符串,把字符串按块翻转,其中连续的小数点为一块,连续的字母为一块。例如 'ab..bc...cd.' 翻转后为 '.cd......

2264
来自专栏aCloudDeveloper

算法导论第十五章 动态规划

      写在前面:从本章开始,算法导论章节进入第四部分:高级设计和分析技术。在读的过程中,可以明显感觉到本章内容跟之前章节的内容要复杂得多。这么来说,之前章...

2645
来自专栏赵俊的Java专栏

搜索二维矩阵Ⅱ

2123
来自专栏Duncan's Blog

回溯法笔记

为了应用回溯法,所要求的解必须能表示成一个n-元组(x1,x2,…,xn),其中xi是取自某个有穷集Si。通常,所求解的问题需要求取一个使某一规范函数P(x1,...

1102
来自专栏机器人网

机器学习中基本的数学符号是什么?

本文介绍了机器学习中的基本数学符号。具体来说有算数符号,包括各种乘法、指数、平方根以及对数;数列和集合符号,包括索引、累加以及集合关系。此外,本文还给出了 5 ...

7796
来自专栏java一日一条

我是如何击败Java自带排序算法的

Java 8 对自带的排序算法进行了很好的优化。对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个...

1211
来自专栏木可大大

算法初体验

在介绍具体算法之前,我先谈一下个人对学习算法的初心。我的初心无非有两点:一,BAT等互联网公司招聘面试时要问算法知识,如果想要进入互联网公司,我就必须学好算法;...

843
来自专栏Code_iOS

算法?

建议数据结构和算法分开来学,这里只有算法,没有什么是数据结构!数据结构在这里; --->> 点我

1773

扫码关注云+社区

领取腾讯云代金券