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

例子:输入

那么从顶部到底部最小的一条路径和为: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%,看来上述方法是有效的。

前面两篇博文中,简要对SDWebImage的缓存部分多线程部分进行了分析。建议在阅读本篇内容前先看下缓存策略那篇,以对SDWebImage的基本内容有所了解。在本篇中,我们将对它的网络策略进行分析。我们知道SDWebImage的主要功能就是从远程主机上下载图片,所以前面的几个策略都是为这一目的提供支持的,而网络策略的好坏将直接决定库的性能。不过SDWebImage以GitHub上接近20000的star数向我们证明了它不俗的实力,下面就让我们一起看看吧。继续阅读