Compute the Number of Ways to Paint the House via Dynamic Progra

  • 时间:2020-09-23 15:50:46
  • 分类:网络文摘
  • 阅读:84 次

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

Example:
Input: n = 3, k = 2
Output: 6
Explanation: Take c1 as color 1, c2 as color 2. All possible ways are:

            post1  post2  post3      
 -----      -----  -----  -----       
   1         c1     c1     c2 
   2         c1     c2     c1 
   3         c1     c2     c2 
   4         c2     c1     c1  
   5         c2     c1     c2
   6         c2     c2     c1

Using Dynamic Programming to Paint the House

In last post: How to Paint The Houses using Minimal Costs via Dynamic Programming Algorithm?, we discuss the algorithm to paint the house with the minimal cost.

In this post, we will discuss using the same Dynamic Programming algorithm to compute the number of different ways to paint the house subject to one criteria: no same colours for 3 consecutive houses in a row.

If we use F(n) to denote the answer, we can easily have the following:

1
2
3
4
F[0] = 0;
F[1] = k;
F[2] = k * k;
F[n] = (k - 1) * (F[n - 1] + F[n - 2]);
F[0] = 0;
F[1] = k;
F[2] = k * k;
F[n] = (k - 1) * (F[n - 1] + F[n - 2]);

It is straightforward to define/compute the first few F values. When we paint the house n, we might have two choices: paint a different colour than house n-1, which will be answer F[n-1]*(k-1) choices, or with the same colour as house n-1, which will be answer F[n-2]*(k-1).

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) {
        vector<int> f(n + 1);
        f[0] = 0;
        if (n == 0) return f[0];
        f[1] = k;
        if (n == 1) return f[1];
        f[2] = k * k;
        if (n == 2) return f[2];
        for (int i = 3; i <= n; ++ i) {
            f[i] = f[i - 1] * (k - 1) + // different color 
                f[i - 2] * (k - 1); // same color
        }
        return f[n];
    }
};
class Solution {
public:
    int numWays(int n, int k) {
        vector<int> f(n + 1);
        f[0] = 0;
        if (n == 0) return f[0];
        f[1] = k;
        if (n == 1) return f[1];
        f[2] = k * k;
        if (n == 2) return f[2];
        for (int i = 3; i <= n; ++ i) {
            f[i] = f[i - 1] * (k - 1) + // different color 
                f[i - 2] * (k - 1); // same color
        }
        return f[n];
    }
};

This DP is a bit alike (not exactly the same as): Derangement Permutation Implementation using R Programming

The above C++ code implements the DP solution that runs at O(N) both in time and space.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Feel Like a Change? Why Not Try the Life of an Expat-preneur?  4 Tech Trends You Need To Get Prepared For  Blogger Sentenced To Two Years In Prison After Insulting Preside  Back to Basics: Blogging and Copyright Infringement  How To Jazz Up That Boring Business Blog  The Life Of A Million-Dollar Blogger  5 Types of Stories You Can Tell About Your Business  The Maximum Average Subtree of a Binary Tree  How to Design a Snake Game?  How to Design a Two-Sum Data Structure? 
评论列表
添加评论