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.

In this article, I will show you how to build your own blog site with Hexo and Minos.

Install Node.js and Git

If you already have both installed on your computers, great! You can skip to Install Hexo.

Node.js

Node.js provides official installer for most platforms.

For installing via package manager, refer to the guide provided by Node.js.

Git

Git also provides official installer for most plaforms.

Install Hexo

Once Node.js is installed, you can install Hexo with npm:

1

$ npm install -g hexo-cli

For MacOS user, if you encounter a permission error, try use sudo together with the command above.

You can check Hexo’s version to see if it’s successfully installed (the version you see may differ from below):

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

Install Minos

Before installing Minos theme, you have to create a Hexo site:

1

$ hexo init my-blog-site

Then go into the site folder (in this case my-blog-site):

1

$ cd my-blog-site

Now install Minos theme:

1

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

Configure Hexo

Only multilingual site related settings are mentioned here. For general configuration, refer to Hexo documentation.

Open the _config.yml file under the root folder of your blog site.

Specify Theme

Set theme to minos:

1
2
3
4

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

Specify Supported Languages

Set language to the languages you want to support. In my case, I want to support both English (en) and Chinese (zh-cn), and English is the default language.

1
2
3

language:
- en
- zh-cn

Note that the values like zh-cn should match exactly the language file name under themes/minos/languages/.

Customize Permalink and New Post Name

Set permalink and new_post_name as below:

1
2
3

permalink: :lang/:title/

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

Configure Minos

In /themes/minos folder, there is an example theme config file named _config.yml.example. Make a copy of it and rename it _config.yml. In our case, this will be the config file for the default language, i.e. English.

Then make another copy from _config.yml.example and rename it _config.zh-cn.yml. This will be the config file for the Chinese version of our site.

Note that now we have three _config.yml files. What is the precedency?

When generating static files, the configuration takes effect in following order:

1. read settings specified in front-matter in invididual posts/pages, override the counterparts in language specific config YAML file
2. if current language is not the default language, read corresponding config file, e.g. _config.zh-cn.yml when the language is zh-cn and override the counterparts in _config.yml in theme folder
3. read _config.yml in theme folder, override the counterparts in _config.yml in Hexo site root folder
4. read _config.yml in Hexo site root folder

I’ll take navigation bar menu links as an example, other fields like title, author, etc. can also be set the same way.

Specify Menus in English

In _config.yml under themes/minos/ folder, set the menus as below (This is only an example, you may want to set it to the menus fulfill your need):

1
2
3
4
5
6

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

Specify Menus in Chinese

In _config.zh-cn.yml under themes/minos folder, set the menus as below:

1
2
3
4
5
6

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

Create New Posts

When creating a new posts, explicitly specify the language of this post, for example:

1

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

This will create a hello-world.md file under source/_posts/en.

1

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

This will create a hello-world.md file under source/_post/zh-cn.

Note that it’s better to keep the same post in different language the same file name, because when a user wants to see a different language version and select target language from UI, Hexo will only prepend the language code, e.g. zh-cn to the post title in the URL address. If the same post of different languages has different file name, Hexo won’t be able to find it.

Limitations

Here are some limitations I find for current version of Hexo (5.4.0) and Minos (2.4.0)

Create New Pages

Creating new pages of language other than the default language doesn’t work, so I created them manually.

Take my about page for example, the folder structure is as below:

1
2
3
4
5
6
7
8

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

Read More

By default, blogs are shown fully in the home page. To enable Read More button in the home page, you have to add <!-- more --> in the .md file. While after you click on it, the page will be redirected to Read More anchor in the blog page, not from the beginning.

I see there are some hexo plugins out there that can help to add excerpt dynamically based on the word count in the blog but not sure if they are compatible with Minos. I’ll try out and update.

Image Preview

Minos by default enables a out-of-box gallery plugin. Any picture files located under source/gallery/ can be used by any post/page directly via following syntax:

1

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

And it can be loaded from the home page successfully.

Though I could put every single picture of my posts in this gallery folder, it is not a good choice to me to manage the images.

I enabled post asset folder in Hexo’s _config.yml:

1

post_asset_folder: true

In this way every post I created will associate with a folder of the same name, for example:

1
2
3
4
5
6

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

I can put all the images belong to this post, e.g. forest.jpeg, in the folder and use it with below syntax:

1

![Forest](forest.jpeg)

Note there is no / before the image file name.

This gives me a more organized structure while it also has a problem: in home page, the images in gallery folder can be renderred but the ones in the post’s folder will break.

The root cause is that in the home page, the src of the image file is still the relative one, i.e. forest.jpeg, but currently we are at the root folder of the site.

Not sure if this is a bug of Hexo or Minos, I’ll dig further and get back.

Update 08/05/2021

This can be fixed by setting following fields in _config.yml under site root folder:

1
2
3
4

post_asset_folder: true
marked:
  prependRoot: true
  postAsset: true

More discussion see Image cannot be load by relative path using markdown syntax

Google AdSense

Minos, unlike NexT, doesn’t support Google AdSense out of the box.

While the author of Minos, ppoffice, has another theme named icarus that supports Google AdSense. I’ll see if I can merge that to Minos.

Deploy the Site

Netlify

Personally I’m a fan of Netlify for frontend stuff. In addition, one advantage of deploying on Netlify is that it supports private GitHub repositories.

1. Create a new site on Netlify
2. Select the repository you want to deploy (link your Netlify account to your GitHub account first if you haven’t done so)
3. Configure the settings, e.g. branch to deploy, build command, publish directory, etc.
4. Click “Deploy site”, sit back and relax, Netlify will do the rest

GitHub

Deploying hexo site on GitHub pages is documented in details in this guide.

Reference

1. Hexo Documentation
2. Minos Documentation
3. A Step-by-Step Guide: Hexo on Netlify