算法之动态规划
算法一直都是我的弱点,因为平时用不到,甚至面试也用不到(问的都是大厂,都去不了)。
现在不能再拖了。必须开始刷leetcode,系统的学一学了。
然而学到动态规划,意识到这可能是算法中最具有价值的算法了。不会动态规划的思想,有些题根本不知道怎么想。所以想记一记,其思想
有价值的链接
思想
算法都是有其固定思路的。动态规划肯定也有。其思想指导如何解决问题。所以,动态规划的套路是:
- 寻找最优解的子问题结构
- 自底向上的方式解决问题
- 定义问题的边界
- 用缓存来记住重复的子问题
接下来用一个经典的爬楼梯问题解释其思想:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
1. 寻找最优解的子问题结构
,
这正是最难的一部分,正是大量需要练习的部分。不同题目的思想转换看附录
题目的意思是,一次可以爬1或者2个台阶,那么到达终点,只能有两种情况:最后一步跳一下
或者两下
。而跳最后一步之前,也可以当作一个完整的爬楼梯问题
,所以也可以用同样的方式分析。那么问题就很清晰的,可以用递归的方式去解决这个问题。
假设跳到第x个台阶发方法为f(x),那么跳到第x个台阶应该是两种情况之和,即:
f(x) = f(x-1) + f(x-2)
2. 考虑问题的边界
第二个步骤是考虑问题的边界,一般动态规划都是递归思想,所以肯定得有个边界,让其停下来。
这问题的边界就是,如果阶梯只有一阶或者两阶。
if (n < 2) return n;
那么问题可以写出来了
1 | /** |
就这么简单。
3. 用缓存来存储重复的子问题
这也是动态规划普遍会遇到的问题。
假如,n=4时,
f(4) = f(3) + f(2);
一直分解下去,则
f(4) = (f(1) + f(2)) + f(2);
这时候就会有两次f(2);
如果参数更大时,重复的子问题会指数级增长。一个简单的办法就是,用个Map来缓存已经计算过的值。用空间换时间。
1 | const store = new Map(); |
这么一来,问题基本解决了。
4. 自底向下解决问题
作为算法学习人员,应该很明显的观察到,这题是个尾递归。尾递归可以转换为循环求解,以达到优化的目的。
这个问题无限拆解下去,最终是f(x) = …+(f(1) + f(2));
所以自底向下解决问题,大概意思是,从f(1)、f(2)这种底部,开始逐步往上求解
那么f(3) = f(2) + f(1)。f(4) = f(3) + f(2);
可以得到
1 | var climbStairs = function (n) { |
这个就是动态规划的终极形态了。不过不是所有的动态规划都可以转换为最终形态。
by the way。这个就是个斐波那契数列
。
结尾
动态规划是一步一步进行的,跳跃思考,可能往往会扯到蛋。而且,不是所有动态规划都可以走到最后一步的终极形态。
所以以后要是遇到类似的题目,应该按部就班的,每一步都要实现出来,不仅思路清晰,稳定。而且可以让面试官了解自己的思路。
附录
买卖股票的最佳时机
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
官方解答是:
我们来假设自己来购买股票。随着时间的推移,每天我们都可以选择出售股票与否。那么,假设在第 i 天,如果我们要在今天卖股票,那么我们能赚多少钱呢?
显然,如果我们真的在买卖股票,我们肯定会想:如果我是在历史最低点买的股票就好了!太好了,在题目中,我们只要用一个变量记录一个历史最低价格 minprice,我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
因此,我们只需要遍历价格数组一遍,记录历史最低点,然后在每一天考虑这么一个问题:如果我是在历史最低点买进的,那么我今天卖出能赚多少钱?当考虑完所有天数之时,我们就得到了最好的答案。
👍
比特位计数
题目: 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
解析:
这题可以用十进制转二进制的方法暴力算出来(Brian Kernighan 算法)。动态规划更佳,其思路是要找到最高有效位
(这是官方的说法)
这里要分析出,每到2的指数倍数(2、4、8、16、32)这些值的二进制肯定是第一位是1,后面都是0,肯定是只有一个1.
如十进制8,二进制是 1000,那么后面的三个0则可以表达1~7。那么十进制9(8+1)则肯定是8的1个数 + 一的1个数。10(8+2),则肯定是8的1个数 + 2的1个数。所以,所有的值都可以从底递推上来。具体看我的记录
✌