Problem

You are painting a fence of n posts with k different colors. You must paint the posts following these rules:

• Every post must be painted exactly one color.
• There cannot be three or more consecutive posts with the same color.

Given the two integers n and k, return the number of ways you can paint the fence.

Example 1:

1
2
3
4

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

Example 2:

1
2

Input: n = 1, k = 1
Output: 1

Example 3:

1
2

Input: n = 7, k = 2
Output: 42

Constraints:

• 1 <= n <= 50
• 1 <= k <= 10⁵
• The testcases are generated such that the answer is in the range [0, 2³¹ - 1] for the given n and k.

Bottom-up Dynamic Programming

Intuition

Right after finish reading the question, I feel I should calculate subproblems of the final problem and the subproblems are overlapped. In addition, the questions asks for number of ways.

These are all signals that indicate this is a dynamic programming question. In general, there are four steps to solve a dynamic programming question:

1. Divide a complex problem into a number of simpler overlapping subproblems
   • some would say this step is to define the optimal solution
2. Define a recurrence relation to solve larger subproblems from smaller subproblems
3. Store solutions to each of these subproblems, solving each subproblem only once
4. Use stored solutions to solve the original problem

Algorithm

1. Let 2D array opt[i][j] denote the optimal number of ways to paint post i with color j

• Initialize the array: for opt[i][j] where i == 0, opt[i][j] = 1 and where i == 1, opt[i][j] = k

2. The recurrence relation for i >= 2 is opt[i][j] = sigma(opt[i-1][!j]) + sigma(opt[i-2][!j])
3. Iterate i from 2 to n-1, build and store the solutions for each subproblem
4. The solution to the original problem is sigma(opt[n-1][j]) where j = [0, k)

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public int numWays(int n, int k) {
        if (n == 1) { return k; }
        if (k == 1) { return n > 2 ? 0 : 1; }
        // define the optimal solution
        int[][] opt = new int[n][k];
        
        // init
        for (int i = 0, j = 0; j < k; j++) {
            opt[i][j] = 1;
        }        
        for (int i = 1, j = 0; j < k; j++) {
            opt[i][j] = k;
        }
        
        // solve subproblems
        for (int i = 2; i < n; i++) {
            int pp = 0, p = 0;
            for (int x = i-1, y = 0; y < k; y++) { p += opt[x][y]; }
            for (int x = i-2, y = 0; y < k; y++) { pp += opt[x][y]; }
            for (int j = 0; j < k; j++) {
                opt[i][j] = p - opt[i-1][j] + pp - opt[i-2][j];
            }
        }
        
        // solve the original problem 
        int numWays = 0;
        for (int i = n-1, j = 0; j < k; j++) { numWays += opt[i][j]; }
        return numWays;
    }
}

Complexity Analysis

Time Complexity

O(n*k)

We iterate n times and each time we calculate the sum of previous row, which is of size k

Space Complexity

O(n*k)

We created a 2D array to store the optimal solution for each subproblem.

Dynamic Programming (Time and Space Improvement)

Intuition

Though it can be accepted by the judge, the first solution is a little time & space consuming. Let’s examine the problem more carefully:

When painting the 1^st post, we have k ways.

When painting the 2^nd post, we have k*k ways, since we can have two consecutive posts colored with the same color.

When painting the 3^rd post, we have to pay attention as the question doesn’t allow three consecutive posts colored with the same color. How do we achieve that?

The answer is simple: break the harmony! Let the last three posts not being able to form the same color. Here is how:

Pick a color that is other than the color of the 2^nd post.

This complies the constraint by the fact that at least the 3^rd post and the 2^nd post are not painted with the same color.

Here don’t waste your time thinking about what exact color the 2^nd post was painted with, otherwise you’ll be swallowed by the black hole (just kidding). Just imagine that the 2^nd post picked one color, then you have k-1 options now. Hence you can paint in k*k * (k-1) ways.

You may ask how about the colors of the 2^nd and the 1^st post in this case, will they be painted with the same color? May be the same maybe not, but we don’t care! It doesn’t break any rule set by the question.

Pick a color that is other than the color of the 1^st post.

This complies the constraint by the fact that at least the 3^rd post and the 1^st post are not painted with the same color.

Same here, just imagine that the 1^st post picked one color, then you have k-1 colors to choose, hence there are 1 * (k-1) ways to paint.

Hence, the optimal number of ways to paint the 3^rd post is k*k * (k-1) + 1 * (k-1), i.e. (k*k + 1) * (k-1).

…

When painting the i^th post, the number of ways is (ways(i-1) + ways(i-2)) * (k-1).

Great! It looks like we don’t need to know the exact color of a post at all in our solution.

Algorithm

1. Let 1D array opt[i] denote the optimal number of ways to paint posts [0,i]
   • Initialzie the array: opt[0] = k and opt[1] = k*k
2. The recurrence relation for i >= 2 is opt[i] = (opt[i-1] + opt[i-2]) * (k-1)
3. Iterate i from 2 to n-1, build and store the solutions for each subproblem
4. The solution to the original problem is opt[n-1]

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int numWays(int n, int k) {
        // corner case
        if (n == 1) return k;
        if (k == 1) return n == 2 ? 1 : 0;
        
        // define the optimal solution
        int[] opt = new int[n];
        
        // init
        opt[0] = k;
        opt[1] = k*k;
        
        // recurrence relation
        for (int i = 2; i < n; i++) {
            opt[i] = (opt[i-1] + opt[i-2]) * (k-1);
        }
        
        return opt[n-1];
    }
}

Complexity Analysis

Time Complexity

O(n)

We traverse the array in one pass.

Space Complexity

O(n)

We create an auxiliary 1D array to store the optimal solution for each subproblem.

Dynamic Programming (Further Space Improvement)

Intuition

In the previous solution, for each subproblem opt[i] we only need to keep opt[i-1] and opt[i-2] in order to calculate its value. We don’t need an array to store each state for this question.

Algorithm

1. Let p be the optimal solution for previous post, and pp be the one before previous post

• Initialzie the variables: pp = k and p = k*k

2. The recurrence relation is the optimal number of ways for the current post is (pp + p) * (k-1)
3. Iterate i from 2 to n-1, caculate optimal solution for current subproblem and shift the values of pp and p
4. The solution to the original problem is p

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int numWays(int n, int k) {
        // corner case
        if (n == 1) return k;
        if (k == 1) return n == 2 ? 1 : 0;
        
        int pp = k, p = k*k;
        
        for (int i = 2; i < n; i++) {
            int cur = (pp + p)*(k - 1);
            pp = p;
            p = cur;
        }
        
        return p;
    }
}

Complexity Analysis

Time Complexity

O(n)

We only have one for loop and in the worse case it has n-2 iterations.

Space Complexity

O(1)

We only create two variables to store the previous state.

在这篇文章里，我会向大家展示如何使用Hexo和Minos搭建支持多语言的博客网站。

安装 Node.js 和 Git

如果你的电脑上已经安装了Node.js和Git，那无敌了，直接跳到安装 Hexo吧.

Node.js

Node.js为大多数平台提供了官方安装器。

如果想要通过package manager安装，可以参考Node.js提供的这份指南。

Git

Git同样也为多数平台提供了官方安装器。

安装 Hexo

Node.js安装完毕后，即可通过使用下面的npm命令安装Hexo：

1

$ npm install -g hexo-cli

对于苹果用户，如果遇到权限问题，可以尝试使用sudo执行上面的命令。

安装结束后可以通过如下命令查看Hexo的版本，以检查Hexo是否安装成功：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

$ hexo -version

hexo-cli: 4.3.0
os: darwin 20.5.0 11.4

node: 14.15.3
v8: 8.4.371.19-node.17
uv: 1.40.0
zlib: 1.2.11
brotli: 1.0.9
ares: 1.16.1
modules: 83
nghttp2: 1.41.0
napi: 7
llhttp: 2.1.3
openssl: 1.1.1g
cldr: 37.0
icu: 67.1
tz: 2020a
unicode: 13.0

安装 Minos

在安装Minos主题前，我们需要先创建一个Hexo网站（文件夹的名字可以按个人喜好命名，此处仅用作举例）：

1

$ hexo init my-blog-site

然后进入到这个my-blog-site文件夹：

1

$ cd my-blog-site

现在我们可以通过如下命令安装Minos主题了：

1

$ git clone https://github.com/ppoffice/hexo-theme-minos.git themes/minos

配置 Hexo

下面的内容仅包含和多语言网站相关的设定。对于其他常见设定，请参考Hexo和Minos的官方文档。

打开博客网站根目录下的_config.yml文件。

指定 Theme

将 theme 设置为 minos:

1
2
3
4

# Extensions
## Plugins: https://hexo.io/plugins/
## Themes: https://hexo.io/themes/
theme: minos

指定支持的语言

将 language 设置为支持的语言。以我为例，我需要支持英文（en）和简体中文（zh-cn）。同时英文是网站的默认语言。

1
2
3

language:
- en
- zh-cn

注意：像zh-cn这类的值必须和主题文件夹下的language文件夹里的语言文件名字一致，包括大小写。

指定链接格式和新文章的文件名

将 permalink 和 new_post_name 设置为如下的值:

1
2
3

permalink: :lang/:title/

new_post_name: :lang/:title.md # File name of new posts

配置 Minos

在 /themes/minos 文件夹下，有一个名为 _config.yml.example 的配置文件. 在同目录下复制一份这个文件并重命名为 _config.yml。 这个文件就是我们网站的默认语言，也就是英文，的主题配置文件。

再在同目录下复制一份配置文件并重新命名为 _config.zh-cn.yml。这个文件就是我们网站中文的主题配置文件。

注意：我们现在有三个 _config.yml 文件了，它们的优先级是怎样的呢？

在生成静态文件的时候，配置是按如下顺序生效的：

1. 如果文章里有front-matter相关的配置，则这部分配置会复写当前语言下的主题配置文件
2. 如果当前语言不是网站默认语言，会再接着读当前语言的主题配置文件，例如_config.zh-cn.yml，这部分配置会复写默认语言的主题配置
3. 接下来是读默认语言的主题配置，这部分会复写对应的网站配置
4. 最后是读取网站的配置

我会以网站的导航菜单栏为例说明如何配置不同语言下的菜单栏，其他的例如网站标题 title 、作者 author 等同理便不再赘述。

设定英文菜单栏

在 themes/minos/ 文件夹下的 _config.yml 文件里, 设置英文菜单栏和对应的路由如下（仅为举例，你的设计可能和我的不同）：

1
2
3
4
5
6

# Navigation bar menu links.
menu:
  Archives: /archives
  Categories: /categories
  Tags: /tags
  About: /about

指定中文菜单栏

在 themes/minos/ 文件夹下的 _config.zh-cn.yml 文件里, 设置如下中文菜单和路由：

1
2
3
4
5
6

# Navigation bar menu links.
menu:
  归档: /zh-cn/archives
  分类: /zh-cn/categories
  标签: /zh-cn/tags
  关于: /zh-cn/about

创建新的博客

当窗前新的博客时，最好明确指明这篇文章对应的语言，例如：

1

$ hexo new post "hello world" --lang en

这样就会在 source/_posts/en 文件夹下生成一个 hello-world.md 文件。

1

$ hexo new post "hello world" --lang zh-cn

这样就会在 source/_posts/zh-cn 文件夹下生成一个 hello-world.md 文件。

注意：最好将不同语言的同一篇文章取一样的.md名字，因为用户在网站的UI上切换语言的时候，Hexo只会在当前的路径前放上对应的语言代码，例如zh-cn。如果两篇文章的文件名不一样，则Hexo显然定位不到对应的文章，从而出现404。

局限性

在搭建过程中，我发现使用当前最新的 Hexo (5.4.0) 和 Minos (2.4.0)还是有一些局限性的。

创建新的页面

在创建非默认语言的页面的时候，Hexo工作并不正常，必须得手动操作达到想要的效果。

就拿“关于”页面为例，文件夹的结构是这样的：

1
2
3
4
5
6
7
8

- source
|-- _posts
|-- about
    |-- index.md
|-- gallery
|-- zh-cn
    |-- about
        |-- index.md

展开阅读

默认情况下主页中显示的博客都是全篇，而非前几段的一个片段。如果想要开启“展开阅读”按钮的话，需要在对应博文的 .md 文件内添加 <!-- more -->，这样Minos会在对应位置插入一个锚点。但是这种情况下在主页点击后页面会被定位在锚点的位置，而非文章的开头。

我知道目前有一些Hexo插件支持基于文章的长度动态生成“展开阅读”按钮，不过我并不确定它们是否和Minos主题兼容。我需要试一下再回来更新。

图片预览

Minos主题默认开启了一个直接可用的图库插件。任何放在 source/gallery/ 文件夹下的插件都可以通过以下语法直接在博文中使用：

1

![](/gallery/a-beautiful-picture.jpeg)

这种方式插入的图片在首页也可以成功加载。

虽然我可以把所有博文的图片都放在 source/gallery 文件夹下，但显然随着文章数量的增加这不利于管理。

我在网站根目录下的 _config.yml 中打开了按博文新建文件夹的开关：

1

post_asset_folder: true

这样每次我创建一篇新的文章时这篇文章都会建立一个同名的文件夹，例如：

1
2
3
4
5
6

- source
|-- _posts
    |-- en
        |-- hello-world
            |-- forest.jpeg
        |-- hello-world.md

我可以将只属于这篇文章的图片，例如forest.jpeg，放在这个文件夹当中，然后使用如下语法将它插入到文章中：

1

![Forest](forest.jpeg)

注意：这里图片文件名前是不带 / 的。

这种设定让我能够更好地组织文件夹结构，但是却引出了一个问题：在主页上，gallery 文件夹里的图片能够正常显示，但博文对应文件夹里的图片却无法加载。

排查下来主要原因是博文对应的图片插入时使用的是相对路径，而在主页下当前路径是跟路径，所以自然找不到博文文件夹中的内容。

我不确定这是Hexo的问题还是Minos的，需要再排查下再回来。

更新 08/05/2021

这个问题可以通过往网站更路径下的 _config.yml 添加如下字段修复：

1
2
3
4

post_asset_folder: true
marked:
  prependRoot: true
  postAsset: true

更多讨论详见 Image cannot be load by relative path using markdown syntax

谷歌 AdSense

Minos主题，不像是NexT主题，默认并不支持谷歌的AdSense。

但是Minos的作者ppoffice创建过另外一个交icarus的主题是支持谷歌AdSense的。我要看看能不能把它移植到Minos上来。

部署网站

Netlify

我个人很喜欢使用Netlify部署前端的东西。另外，部署在Netlify上的一个很突出的优势是我们的GitHub仓库不需要是公开的。

1. 在Netlify上创建一个新的网站
2. 选择你想要部署的仓库（你的Netlify账号需要先和GitHub建立链接，授权操作）
3. 配置相关设定，如部署哪个分支、生成命令和发布文件夹等等
4. 点击“Deploy Site”，剩下的就交给Netlify吧

GitHub

这篇指南详细介绍了如何将Hexo网站部署在GitHub上。

参考

1. Hexo官方文档
2. Minos官方文档
3. A Step-by-Step Guide: Hexo on Netlify