前言
本文以一道 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, 考虑初始状态和边界情况
四, 另一个经典的例子 -- 数塔
有如图所示的数塔, 要求从顶层走到底层, 若每一步只能走到相邻的结点, 则经过的结点的数字之和最大是多少?
题目链接点这里 http://acm.hdu.edu.cn/showproblem.php?pid=2084
解决思路:
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 背包" 这三个题目, 能解决算法面试的动态规划部分.
来源: http://www.jianshu.com/p/919cd4e268b1