不会飞的章鱼

计算器程序的功能设计

一般计算器功能如下：

• 第一次出现的变量赋值语句，即为变量定义；
• 计算表达式的值。

这两个功能，看似简单，可实际要考虑的还很多，例如：变量是否有作用域的限制啊，合法变量名的规则，表达式中支持的运算符种类啊，每一种运算符的优先级，等等。这些需要考虑的细节，每一个都会给我们的项目增加一点点难度。

为了把难度控制在一个可以实现的范围，我们对计算器功能做进一步的细致描述，同时也是降低项目实现难度，重新修订的功能定义如下：

初识：0/1 背包问题

0/1 背包问题可以说是所有背包问题的基础，它描述的场景是这样的：假设你有一个背包，载重上限是 W，你面前有 n 个物品，第 i 个物品的重量是 wi，价值是 vi，那么，在不超过背包重量上限的前提下，你能获得的最大物品价值总和是多少？

按照动态规划问题的四步走，咱们来分析一下这个问题。

状态定义

关于状态定义，我们首先来分析 0/1 背包问题中的自变量和因变量。

任务

数字三角形问题

由上到下，第 i 层由 i 个数字组成，目标从第 1 层开始，每次只能向下走到相邻的两个节点，求走到最后一层路径上面数字的最大和值是多少。就像图中标红的一条线路，就是路径和值最大的一条路线，和值为 39。如果给你的是一个 n 层的数字三角形，你该如何解决这个问题呢？

数学归纳法思想

任务

众所周知，在不计算小于 1 元钱的面额的前提下，我国的纸币系统中，曾经拥有如下面值：1 元、2 元、5 元、10 元、20 元、50 元 和 100 元。假设，每一种面值的纸币，我们都有无限张，现在想用这些钱凑出 1000 元，请问你有多少种不同的方案？

这里说的不同方案，是不关注钱币之间的顺序的，例如要凑 7 元钱，可以是 1 元、5 元、1 元，也可以是 1 元、1 元、5 元，这两种方案我们视为同一种。

编码实现

容斥原理

任务

假设有一面木板墙，每块木板的宽度都是 1，你现在想在木板墙上，沿着平行于地面的方向，切割出一块矩形区域。问题来了，如果给出了每一块木板的高度，那么如何切出面积最大的矩形区域？矩形木板墙如下图所示：

思考

图中有 7 块木板，每块木板的高度分别为：2、1、4、5、1、3、3。经过尝试，我们发现最大矩形就是红色阴影部分所示，也就是切割了高度为 4 和 5 两块木板，形成了一个高度为 4，宽度为 2 的矩形区域，这个最大面积为 8。

今天看了天气，不是很热，和女朋友计划去龙潭水乡玩一玩。

坐车大概花了一个半小时，因为是快速公交，时间上节约了大概半小时。

到达指定地点后，哇，人很少，很有江南水乡的气息，和小学语文课本上见到的一样呢。

到处都是桥，路面凹凸不平，水面上的荷花很好看，景区内也有穿着汉服拍照的小哥哥小姐姐。

我和她选择了一些人比较少的地方取景，摆姿势，不得不说，自己私底下看了看讲拍摄的文章，还是很有用，女朋友夸我拍照技术也进步了，哈哈。(可想而知以前在拍照上打击的有多惨～～～)

任务

滑动区间最大值，就是指在固定区间长度的前提下，在一个序列上，从前到后滑动这个区间窗口，每次窗口内部的最大值，就组成了滑动区间最大值。

例如，给你如下包含 8 个数字的序列，区间长度设置为 3：

1
2
3
4
5
6

[6 4 2] 10 3 8 5 9 -> 6
6 [4 2 10] 3 8 5 9 -> 10
6 4 [2 10 3] 8 5 9 -> 10
6 4 2 [10 3 8] 5 9 -> 10
6 4 2 10 [3 8 5] 9 -> 8
6 4 2 10 3 [8 5 9] -> 9

滑动区间从数字 6 开始出发，每次向右移动一个数字，同时把左边的一个数字丢出去，保持区间长度为 3，最后移动到数字 9 停止。可以看到，这个序列共包含 8 个数字，所以最后形成的滑动区间最大值共有 6 个，依次是 6、10、10、10、8、9。

百度网盘上的视频无法变速，我将分享一种我自认为最快解决的办法。

步骤一：添加快捷指令

打开iPad上的快捷指令；
选中共享表单快捷指令；
点击更改视频速度；
拉到最下面点击添加快捷指令。

步骤二：Safari浏览器

打开Safari浏览器，登录百度网盘，选中一个视频播放；
点击右上角有一个向上箭头的图标；
拉到下面有一个更改视频速度的选项；
选择可以接受的视频播放速度，完成。

任务

首先，我们定义一种数字名称，叫做“快乐数”。所谓快乐数就是经过有限次变换以后，等于 1 的数字。这个变换规则，给出一个非 1 的数字 a ，把它的位数拎出来，求各个位数的平方和，得到一个数字 b，如果数字 b 不是 1，那就对数字 b 的每一位数再做平方和，得到数字 c……经过不停的变换，确定最后能否得到 1。

例如，一开始的数字是 19，经过变换规则 12+92=82，得到数字 82；因为不是 1 ，所以接着做变换，就是 82+22=68，再做一次变换 62+82=100，最后一次做变换 12+02+02=1，得到了 1 以后，停止。

注：此题LeetCode链接

实现

任务

假设你手上有 n 段长度不等的绳子，你现在想将这些绳子进行裁剪，裁剪出 k 条长度相等的绳子，注意，只能剪断绳子，不能拼接绳子。问题就是，你能得到的这 k 段绳子的最长长度是多长？

如图所示，如果你手中有 3 条绳子，分别是 4 米、6 米 和 5 米，想要切出等长的 4 段，你会发现，每段最长就是 3 米。

思考