算法之动态规划

算法之动态规划

五月 14, 2021

算法一直都是我的弱点,因为平时用不到,甚至面试也用不到(问的都是大厂,都去不了)。
现在不能再拖了。必须开始刷leetcode,系统的学一学了。

然而学到动态规划,意识到这可能是算法中最具有价值的算法了。不会动态规划的思想,有些题根本不知道怎么想。所以想记一记,其思想

有价值的链接

leetcode-爬楼梯

掘金-漫画讲解动态规划

思想

算法都是有其固定思路的。动态规划肯定也有。其思想指导如何解决问题。所以,动态规划的套路是:

  1. 寻找最优解的子问题结构
  2. 自底向上的方式解决问题
  3. 定义问题的边界
  4. 用缓存来记住重复的子问题

接下来用一个经典的爬楼梯问题解释其思想:

假设你正在爬楼梯。需要 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
2
3
4
5
6
7
8
9
/**
* @param {number} n
* @return {number}
*/
function clibStairs(n) {
if(n < 2) return n;

return clibStairs(n - 1) + clibStairs(n - 2);
}

就这么简单。

3. 用缓存来存储重复的子问题

这也是动态规划普遍会遇到的问题。

假如,n=4时,

f(4) = f(3) + f(2);

一直分解下去,则

f(4) = (f(1) + f(2)) + f(2);

这时候就会有两次f(2);
如果参数更大时,重复的子问题会指数级增长。一个简单的办法就是,用个Map来缓存已经计算过的值。用空间换时间。

1
2
3
4
5
6
7
8
9
10
11
12
const store = new Map();
function clibStairs(n) {
if(n < 2) return n;

const cache = store.get(n);
if(cache) return cache;

const result = clibStairs(n - 1) + clibStairs(n - 2);
store.set(n, result);

return result;
}

这么一来,问题基本解决了。

4. 自底向下解决问题

作为算法学习人员,应该很明显的观察到,这题是个尾递归。尾递归可以转换为循环求解,以达到优化的目的。

这个问题无限拆解下去,最终是f(x) = …+(f(1) + f(2));

所以自底向下解决问题,大概意思是,从f(1)、f(2)这种底部,开始逐步往上求解

那么f(3) = f(2) + f(1)。f(4) = f(3) + f(2);

可以得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var climbStairs = function (n) {
if (n < 2) return n;

let a = 1;
let b = 2;
let result = 2;
while(n > 2) {
result = a + b;

// 计算完结果后,向前挪一步。
a = b;
b = result;
n--;
}
return result;
};

这个就是动态规划的终极形态了。不过不是所有的动态规划都可以转换为最终形态。
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个数。所以,所有的值都可以从底递推上来。具体看我的记录