题意:给出 n 组数,每组有两个数,第一个数总是比第二个数字小。如果两组数 (a,b) 和 (c,d) 之间,有 b < c,那么就称 (a,b)和 (c,d) 之间形成了一个chain。求出这 n 组数中能形成的最长的 chain 的长度。

例子:输入[[1,2], [2,3], [3,4]],因为[1,2] -> [3,4],所以返回2。继续阅读

这个题也是一道动态规划题目。题意是:给出一系列数和一个目标数,使用+-来使这些数字的和等于给定的目标数,求总共可行的方法数。

例子:输入[1, 1, 1, 1, 1]target = 3,那么:

所以最后的输出结果是:5继续阅读

这道题的题意是:给定一个数组形成的三角形,在从三角形的顶部出发的路径中,求节点数值相加结果为最小的和。

例子:输入

那么从顶部到底部最小的一条路径和为:2+3+5+1=11

思路:这是一道逆序的二维动态规划题,和之前看过的一道题–《龙与地下城》非常相似,都是逆序地从下往上求 DP数组。代码很简单,就不多做分析了,相信大家一看就能看懂。

代码如下:

链接在此。

解题思路:输入的 cost 向量的长度 len即为台阶的级数。我们可以生成一个长度为len+1的向量 dp,dp[i]表示跳到第 i 个位置(从0开始计数)需要的费用。例如 dp[0]表示跳到第0个位置的cost,为0;dp[1]表示跳到第1个位置的 cost,因为起始 index 可以为1,所以 dp[1] = 0;dp[2]表示跳到第2个位置的 cost,因为一次可以跳一步或者两步,因此 dp[2]的值有两种可能:

* 从第0个位置跳过来,所以 dp[2] = dp[0] + cost[0];
* 从第1个位置跳过来,所以 dp[2] = dp[1] + cost[1];
因此我们应该取这两种情况中较小的那一个:dp[2] = min(dp[2-2] + cost[2-2], dp[2-1]+cost[2-1]);

下面我们来推导状态转移方程:
dp[i]表示跳到第 i 个位置,它的值有两种可能:
* 从第 i-2 个位置跳过来,因此dp[i] = dp[i-2]+cost[i-2]
* 从第 i-1 个位置跳过来,因此dp[i] = dp[i-1]+cost[i-1]

因此,dp[i] = min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2])。这即为本题的状态转移方程。根据该方程,我们不难写出下面的代码:

我的电脑是 Macbook Pro (Retina, Early 2015)款,最近遇上了几次合盖前电量90+,睡眠一两天后再打开电量耗尽的现象。第一次我打了电话给技术支持,但是没有得到任何有效的建议。而今早我的 MacBook 又出现了这种现象,在网上搜索一番后,我找到了如下的解决方案

  1. 重启 Macbook,在启动的时候按住 command + R,等待一会后系统会进入 Recovery 模式。
  2. 从菜单栏的实用工具中选择打开终端。
  3. 输入 csrutil disable 禁掉 SIP,然后正常重启 Macbook。
  4. 打开终端,输入 ioreg -l | grep board-id 查看并记住这个board-id。
  5. 打开 Finder,按住 command+shift+g,进入目录 /System/Library/Extensions/IOPlatformPluginFamily.kext/Contents/PlugIns/X86PlatformPlugin.kext/Contents/Resources,然后找到上一步中的 board-id 对应的 .plist 文件。
  6. 用管理员权限编辑该 plist 文件。
  7. TCPKeepAliveDuringSleep 修改为 false, 然后保存。
  8. 重启 MacBook,再次进入 Recovery 模式,打开终端输入csrutil enable以重启SIP服务。

最近几次电脑睡眠后,再打开时电量相比睡眠前只下降1%~2%,看来上述方法是有效的。