LeetCode 276. Paint Fence (Counting DP)

 276. Paint Fence

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:

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:

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

Example 3:

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

 

Constraints:

• 1 <= n <= 50
• 1 <= k <= 105
• The testcases are generated such that the answer is in the range [0, 231 - 1] for the given n and k.

	class Solution {
	public:
	/*
	Framework DP (with Counting DP)
	1. function
	- state vars
	- i: i th post
	- k: current color's consecutive count
	- dp[i][c]: i th post
	- answer: sum(dp[n-1][c]) c = [1, 2]
	2. relation
	(c == 2 same color) dp[i][c] = dp[i-1][1]
	(c == 1 diff color) dp[i][c] = dp[i-1][1] * (k - 1) + dp[i-1][2] * (k - 1)
	3. base
	dp[1][1] = k
	(i < c) 0
	(i = 0 or c = 0) 0
	*/
	vector<vector<int>> memo;
	int k;
	int dp(int i, int c){
	if(c == 0) return 0;
	if(i == 0) return 0;
	if(i < c) return 0;
	if(i == 1 and c == 1) return k;
	if(memo[i][c] == -1){
	if(c == 2)
	memo[i][c] = dp(i-1, 1);
	else
	memo[i][c] = dp(i-1, 2) * (k - 1) + dp(i-1, 1) * (k-1);
	}
	return memo[i][c];
	}
	int numWays(int n, int k) {
	this->k = k;
	memo.resize(n + 1, vector<int>(3, -1));
	return dp(n, 1) + dp(n, 2);
	}
	};

view raw 276. Paint Fence.cpp hosted with ❤ by GitHub