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

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

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) —

推荐阅读:
各种数的读法和写法  关于分数和百分数的知识点  关于小数的知识点  有关整数的知识点  比较平均数、中位数、众数的特点  小学统计图的种类及特点  小学常用图形计算公式表  小学数学量的计量单位及进率归类  有关比的知识概念  让世界充满爱 
评论列表
添加评论