程序员算法基础——动态规划

前言

本文以一道BAT常见的算法面试题开篇,引入动态规划的基础概念, 介绍其思考过程。

正文

一、BAT最常见的一道算法面试题——上台阶

有一个楼梯总共n个台阶,只能往上走,每次只能上1个、2个台阶,总共有多少种走法。

解决方案: 1、排列组合; 枚举2的个数,再枚举2具体放的位置; 计算复杂,容易遗漏。

2、动态规划; dp[n] 表示n个台阶的走法,那么有: dp[n]=dp[n-1]+dp[n-2]; 思路清晰,代码简单。

二、动态规划基础概念

1、动态规划; 动态规划(Dynamic Programming)指的是解最优化问题的一种方法。

2、最优子结构性质; 问题的最优解可以分解为若干子问题,且子问题的解也是最优的; 以上台阶为例,到第i层的最多走法,可以分解为第i-1层和第i-2层的走法之和,且第i-1层和第i-2层的走法也是最多的;

3、 无后效性; 现阶段的决策不会影响未来的决策; 以上台阶为例,走到第i-2层的最多走法,不会因为增加第i-1层而改变;

三、动态规划思考过程

动态规划的思考过程可以总结为:大事化小,小事化了。 大事化小: 一个较大的问题,通过找到与子问题的重叠,把复杂的问题划分为多个小问题,也称为状态转移; 小事化了: 小问题的解决通常是通过初始化,直接计算结果得到;

具体的步骤

  • 1、将大问题分解为子问题
  • 2、确定状态表示
  • 3、确定状态转移
  • 4、考虑初始状态和边界情况

四、另一个经典的例子——数塔

有如图所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?

题目链接点这里

解决思路: 1、大事化小。要到达第i层,先要到达第i-1层。并且第i层的第j个节点,只能由i-1层的第j个和第j-1个节点到达。 我们用dp[i][j]表示,走到第i层第j个位置的数字最大和。 那么有dp[i][j]=max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];

2、小事化了。第1层的第1个节点,初始值为dp[1][1]=a[1][1]。(a[x][y]表示第x层,第y个的值)

五、数塔例子的变形——收集苹果

平面上有N*M个格子,每个格子中放着一定数量的苹果。 你从左上角的格子开始,每一步只能向下走或是向右走,每次走到一个格子上就把格子里的苹果收集起来。 这样下去,你最多能收集到多少个苹果。

解决思路: 1、只能向右走或者向下走,要到达第i行第j列的格子的时候,可以由第i-1行第j列或者第i行第j-1列到达,我们用dp[i][j]表示,走到第i行第j列的最多苹果数,那么有: dp[i][j]=max(dp[i-1][j], dp[i][j-1]) + a[i][j];

2、第1行第1列,初始值为dp[1][1]=a[1][1],注意事项是边界条件的处理。

六、动态规划经典——01背包问题

给定n件物品和一个容量为m的背包,每件物品都会消耗背包的一定容积c[i],并带来一定价值v[i],要求如何选取装入背包中的物品,使得背包内的物品价值最大。

解决思路: 把n件物品放入背包,可以分解为“将前i件物品放入容量为m的背包中”问题。 若只考虑第i件物品的选择,那么问题可以分为两种情况: 1、如果不放第i件物品,问题就转化为“前i-1件物品放入容量为v的背包中”; 2、如果放第i件物品,问题就转化为“前i-1件物品放入剩下的容量为m-c[i]的背包中”

我们用f[i][j]表示前i个物品,放入容量为j的背包的最大价值,上面的两种情况可以表示为 f[i][j] = max(f[i-1][j], f[i-1][j-c[i]]+v[i]);

初始化条件memset(dp, 0, sizeof(dp));dp[1][c[1]]=v[1]。 最后遍历f[n][1~m]可以得到最大值。

总结

如果还不能完全理解01背包,那么还需要再仔细理解最优子结构状态表示状态转移。 算法能扩展思考方向,完善思维能力。学会“上台阶”、“数塔”、“01背包”这三个题目,能解决算法面试的动态规划部分。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨建荣的学习笔记

字符画,你可能未知的美 (76天)

在平时的工作中,如果接触字符界面时间比较长的时候,都会无意识的感觉到单调,认为字符只能表达一些抽象复杂的东西,对于图形的那种简单和清晰,显得有些力不从心。 今天...

2725
来自专栏北京马哥教育

使用 Python 分析 14 亿条数据

Google Ngram viewer是一个有趣和有用的工具,它使用谷歌从书本中扫描来的海量的数据宝藏,绘制出单词使用量随时间的变化。举个例子,单词 Pytho...

760
来自专栏鹅厂优文

游戏人工智能 读书笔记 (五) AI算法简介——树搜索

本书英文版: Artificial Intelligence and Games - A Springer Textbook

1725
来自专栏JackieZheng

Java豆瓣电影爬虫——使用Word2Vec分析电影短评数据

  在上篇实现了电影详情和短评数据的抓取。到目前为止,已经抓了2000多部电影电视以及20000多的短评数据。   数据本身没有规律和价值,需要通过分析提炼成知...

4068
来自专栏机器人网

滚珠丝杠你知多少,滚柱丝杠你又知多少?

滚珠丝杠的是将螺杆轴与螺母滚道内装进钢珠后进行无限的滚动和循环的一种机械形式,从而产生将旋转运动转化为精确直线定位运动。为减少钢珠在滚道内循环时产生的摩擦力矩,...

3359
来自专栏数说工作室

哈希函数的套路 | 文本分析:大规模文本处理(1)

这个系列打算以文本相似度为切入点,逐步介绍一些文本分析的干货。 第一篇中,介绍了文本相似度是干什么的; 第二篇,介绍了如何量化两个文本,如何计算余弦相似度,穿...

4148
来自专栏工科狗和生物喵

【机器视觉与图像处理】基于MATLAB的角度计算

我一开始还苦思冥想,不知道怎么才能提取出来这个因素,所以很是烦恼不知道该如何是好,但是昨天看了下群里面的说法,我瞬间就理通了。只要转变下思维,把图像看成一个二维...

781
来自专栏工科狗和生物喵

【机器视觉与图像处理】基于MATLAB的角度计算

正文之前 最近新开了一门课,我十分感兴趣,或者是说老早就想接触类似方面的学习,但是一直没有真正着手,所以说,其实上课还是很有必要的,很多时候你想做的事情但是你根...

3399
来自专栏数据魔术师

运筹学教学 | 十分钟快速掌握最短路算法(附C++代码及算例)

最近被BOSS抽查 运筹学 基本功课, 面对BOSS的突然发问, 机智的小编果断选择了—— 拿 · 出 · 课 · 本 然后BOSS 微微一笑 : “来,实现下...

4848
来自专栏张俊的专栏

【SPA大赛】机场客流量的时空分布预测比赛经验分享

1. 问题描述机场拥有巨大的旅客吞吐量,与巨大的人员流动相对应的则是巨大的服务压力。安防、安检、突发事件应急、值机、行李追踪等机场服务都希望能够预测未来的旅客吞...

4590

扫码关注云+社区