Tag Archives: DP

LeetCode Maximum Length of Subarray With Positive Product

1567. Maximum Length of Subarray With Positive Product

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Example 4:

Input: nums = [-1,2]
Output: 1

Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

给一个数组,包含正数、负数和0,问最长连乘结果为正的长度是多少。

本题与LeetCode Maximum Product Subarray类似,要注意负负得正的情况。首先是传统DP好理解方法:设置dp_pos和dp_neg两个数组,分别表示遍历到i时,当前的最长连乘为正的长度和最长连乘为负的长度。则对于第i个位置,如果nums[i]是正数,则dp_pos直接+1;对于dp_neg,如果前一刻已经是连乘为负,即dp_neg[i-1]>0,则在前一刻基础上再乘以nums[i]还是负,所以负数长度可变长,即dp_neg+1;如果前一刻没有连乘为负,则增加一个正数也不会使连乘为负的长度增加,所以dp_neg=0。类似的可以讨论num[i]为负数的情况。如果nums[i]==0,则dp_pos和dp_neg都重置为0。

完整代码如下:

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp_pos(n, 0), dp_neg(n, 0);
        if(nums[0] > 0) dp_pos[0] = 1;
        else if(nums[0] < 0) dp_neg[0] = 1;
        int ans = dp_pos[0];
        for(int i = 1; i < n; ++i) {
            if(nums[i] > 0) {
                dp_pos[i] = dp_pos[i - 1] + 1;
                dp_neg[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
            } else if(nums[i] < 0) {
                dp_pos[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
                dp_neg[i] = dp_pos[i - 1] + 1;
            }
            ans = max(ans, dp_pos[i]);
        }
        return ans;
    }
};

本代码提交AC,用时268MS。

因为DP只用到上一刻的状态,所以不用数组存储也可以,节省内存版本如下,不过需要注意tmp=pos_len保存上一刻的pos_len状态。

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        int pos_len = 0, neg_len = 0;
        if(nums[0] > 0) pos_len = 1;
        else if(nums[0] < 0) neg_len = 1;
        int ans = pos_len;
        for(int i = 1; i < n; ++i) {
            if(nums[i] > 0) {
                ++pos_len;
                neg_len = neg_len > 0 ? neg_len + 1 : 0;
            } else if(nums[i] < 0) {
                int tmp = pos_len;
                pos_len = neg_len > 0 ? neg_len + 1 : 0;
                neg_len = tmp + 1;
            } else if(nums[i] == 0) {
                pos_len = neg_len = 0;
            }
            ans = max(ans, pos_len);
        }
        return ans;
    }
};

本代码提交AC,用时368MS。

剑指 Offer 14- I. 剪绳子 LCOF

剑指 Offer 14- I. 剪绳子 LCOF

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示:

2 <= n <= 58
注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一根长为n的绳子,剪成m段,使得m段长度的乘积最大。问最大乘积是多少。

看题解,把长度切分为3,乘积最大。需要用到算术几何平均不等式,以及求导求极值等数学知识。

完整代码如下:

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int m = n / 3;
        if(n % 3 == 0) {
            return pow(3, m);
        } else if(n % 3 == 1) {
            return pow(3, m - 1) * 4;
        } else {
            return pow(3, m) * 2;
        }
    }
};

本代码提交AC,用时0MS。

另一个通用解法是DP,假设dp[i]是长度为i,切分之后的最大乘积。则对于dp[j],可以把[1,…,j]切分为[1,…,k]和[k+1,…,j],因为切分之后两段的长度都小于j,所以之前已经求解过了,可直接得到乘积。题解如下: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/shu-xue-zhi-shi-he-dong-tai-gui-hua-liang-chong-fa/ 。完整代码如下:

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i) {
            for(int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
            }
        }
        return dp[n];
    }
};

本代码提交AC,用时4MS。

剑指 Offer 10- II. 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2
示例 2:

输入:n = 7
输出:21
示例 3:

输入:n = 0
输出:1
提示:

0 <= n <= 100
注意:本题与主站 70 题相同:https://leetcode-cn.com/problems/climbing-stairs/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


对于跳到第n的位置,有两种来源,如果这一跳是2步,则f(n)=f(n-2),如果这一跳是1步,则f(n)=f(n-1),所以总的情况是f(n)=f(n-2)+f(n-1),也就是求斐波那契数列的第n项。

完整代码如下:

class Solution {
public:
    int numWays(int n) {
        if(n == 0) return 1;
        if(n == 1) return 1;
        if(n == 2) return 2;
        int a = 1, b = 2;
        for(int i = 3; i <= n; ++i) {
            int tmp = (a + b) % 1000000007;
            a = b;
            b = tmp;
        }
        return b;
    }
};

本代码提交AC,用时0MS。

剑指 Offer 10- I. 斐波那契数列

剑指 Offer 10- I. 斐波那契数列

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1
示例 2:

输入:n = 5
输出:5
 

提示:

0 <= n <= 100
注意:本题与主站 509 题相同:https://leetcode-cn.com/problems/fibonacci-number/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


求斐波那契数列的第n项。看之前的POJ题解: http://code.bitjoy.net/2017/05/04/poj-3070-fibonacci/

一共有三种解法。常规解法就是无脑递归调用。关键是如何分析这种解法的时空复杂度。无脑调用是F(n)=F(n-1)+F(n-2)。想象一下,递归调用二叉树( https://wmjtxt.github.io/2018/12/26/three_method_of_fibonacci/ )。每个节点都会分裂出2个孩子,然后孩子继续2倍分裂,所以总调用次数大概是$O(2^n)$,这是时间复杂度。空间复杂度就是递归调用的栈深度,就是树的高度,大概是$O(n)$。

常规解法是,DP的思路,每次保留数列前两项,然后不断更新这两个数。时间复杂度是$O(n)$,空间复杂度是O(1)。完整代码如下:

class Solution {
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        long long a = 0, b = 1;
        for(int i = 2; i <= n; ++i) {
            long long tmp = a + b;
            tmp %= 1000000007;
            a = b;
            b = tmp;
        }
        return b;
    }
};

本代码提交AC,用时0MS。

最优的解法是矩阵快速幂的方法,求矩阵[[1,1],[1,0]]的n次幂,然后矩阵逆对角线位置的值就是F(n)的值。快速幂可以做到$O(lg(n))$的时间复杂度,完整代码如下:

typedef long long LL;

class Solution {
private:
    vector<vector<LL>> multiply(vector<vector<LL>> &m1, vector<vector<LL>> &m2) {
        int n = m1.size();
        vector<vector<LL>> ans(n, vector<LL>(n, 0));
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                for(int k = 0; k < n; ++k) {
                    ans[i][j] += m1[i][k] * m2[k][j] % 1000000007;
                }
            }
        }
        return ans;
    }
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;

        vector<vector<LL>> matrix = {{1,1},{1,0}};

        vector<vector<LL>> ans = {{1,0},{0,1}};
        while(n != 0) {
            if(n % 2 == 1) ans = multiply(ans, matrix);
            matrix = multiply(matrix, matrix);
            n >>= 1;
        }

        return ans[0][1] % 1000000007;
    }
};

本代码提交AC,用时4MS。

LeetCode Maximum Sum Circular Subarray

918. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Note:

  1. -30000 <= A[i] <= 30000
  2. 1 <= A.length <= 30000

给定一个循环数组,即数组的最后一个和数字第一个连起来了。求循环数组的最大连续子数组和。

LeetCode Maximum Subarray的升级版,即数组首尾相连了。我一开始想到的解法是,既然数组首尾相连了,那就2*n次dp即可,即把原数组复制一遍,接到原数组后面,形成2*n长的数组,然后照样跑原来的DP算法。这个解法是不对的,比如如果数组是[1,2,3,4]这种全是正数,则跑2n遍之后,ans会一直max更新,导致最后的ans是1+…+4+1+…4,即数组加了两遍,每个数重复加了。另外对于数组[5,-3,5]这种,也会完整数组加两遍。

正确解法是,分两种情况,第一种情况是最大子串和没有跨越首尾,则使用常规DP即可求解。第二种情况是,最大子串和跨越了首尾,则可以把问题转化为求原数组的最小连续子串和,然后用数组总和减去最小连续子串和,就能得到跨越首尾的最大连续子串和。在求解第二种情况时,需要注意如果最小连续子串和是整个数组的情况,比如数组都是负数[-1,-2,-3],则求到的最小连续子串和是整个数组[-1,-2,-3],用数组总和一减变成了空集和为0,但最大连续子串和至少需要1个元素,对于这种情况,丢弃case2的解。

完整代码如下:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        vector<int> dp(n, 0);
        
        // 最大连续子串
        dp[0] = A[0];
        int ans1 = A[0], sum = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = max(dp[i - 1], 0) + A[i];
            ans1 = max(ans1, dp[i]);
            
            sum += A[i];
        }
        
        // 最小连续子串
        fill(dp.begin(), dp.end(), 0);
        dp[0] = A[0];
        int ans2 = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = min(dp[i - 1], 0) + A[i];
            ans2 = min(ans2, dp[i]);
        }
        
        if(ans2 == sum) ans2 = INT_MIN; // 注意最小连续子串和不能是全长数组
        else ans2 = sum - ans2;
        
        return max(ans1, ans2);
    }
};

本代码提交AC,用时252MS。

LeetCode Coin Change 2

518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Note:

You can assume that

  • 0 <= amount <= 5000
  • 1 <= coin <= 5000
  • the number of coins is less than 500
  • the answer is guaranteed to fit into signed 32-bit integer

给定一堆不同面值的硬币,问凑齐amount块钱,有多少种不同的凑齐方案。

LeetCode Coin Change类似,也用动态规划。假设dp[i][j]表示用前i硬币,凑齐j块钱的方案数。则有两种情况,一是不用第i类硬币,有dp[i-1][j]种情况;二是用第i类硬币,则还需要凑齐j-coins[i]块钱,因为每类硬币无穷个,所以还是用前i类硬币凑齐j-coins[i]块钱,即有dp[i][j-coins[i]]种情况。两种情况数相加即可。完整代码如下:LeetCode Coin Change与

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        if(amount == 0) return 1;
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        for(int i = 0; i <= n; ++i) dp[i][0] = 1;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= amount; ++j) {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
};

本代码提交AC,用时60MS。

LeetCode Max Dot Product of Two Subsequences

1458. Max Dot Product of Two Subsequences

Given two arrays nums1 and nums2.

Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

Example 1:

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

Example 2:

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.

Example 3:

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

Constraints:

  • 1 <= nums1.length, nums2.length <= 500
  • -1000 <= nums1[i], nums2[i] <= 1000

给定两个数组,问从这两个数组中选出两个长度相同的子序列,使得子序列的向量点积最大,求这个最大值。

难题,参考讨论区解法: https://leetcode.com/problems/max-dot-product-of-two-subsequences/discuss/648261/C++Python-Simple-DP

假设dp[i][j]表示nums1[0:i]和nums2[0:j]的最大点积。则在求解dp[i][j]时,有以下四种情况:

  • 不选nums1第i个数,dp[i][j]=dp[i-1][j]
  • 不选nums2第j个数,dp[i][j]=dp[i][j-1]
  • 既不选nums1第i个数,也不选nums2第j个数,dp[i][j]=dp[i-1][j-1]
  • 既选nums1第i个数,也选nums2第j个数,dp[i][j]=dp[i-1][j-1]+nums1[i]*nums2[j]

在最后一个情况中,如果dp[i-1][j-1]<0的话,就把前面的点积都扔掉,相当于max(dp[i-1][j-1],0),完整代码如下:

class Solution {
public:
	int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));
		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
				dp[i][j] = max(dp[i][j], dp[i][j - 1]);
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
				dp[i][j] = max(dp[i][j], max(dp[i - 1][j - 1], 0) + nums1[i - 1] * nums2[j - 1]);
			}
		}
		return dp[m][n];
	}
};

本代码提交AC,用时96MS。

LeetCode Maximum Points You Can Obtain from Cards

1423. Maximum Points You Can Obtain from Cards

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

给定一个数组,要从中选k个数,每次只能从左边选或从右边选,问选出的数的和最大是多少。

转换思路,无论从左边选多少个,从右边选多少个,剩余的数都是中间区域的某一段数。要使选出来的数和最大,则相当于要使剩下的连续区间的数和最小。所以可以设置一个大小为n-k的滑动窗口,求该滑动窗口的最小和,则用总和减去该最小和即为最终结果。

完整代码如下:

class Solution {
public:
	int maxScore(vector<int>& cardPoints, int k) {
		int sum = 0, n = cardPoints.size();
		for (int i = 0; i < n; ++i)sum += cardPoints[i];
		if (k == n)return sum;

		int min_window_sum = 0, i = 0, j = n - k - 1;
		for (int k = i; k <= j; ++k)min_window_sum += cardPoints[k];
		int cur_window_sum = min_window_sum;
		while (j < n) {
			if (j == n - 1)break;
			cur_window_sum = cur_window_sum + cardPoints[++j] - cardPoints[i++];
			min_window_sum = min(min_window_sum, cur_window_sum);
		}
		return sum - min_window_sum;
	}
};

本代码提交AC,用时152MS。

我之前的想法一直是正向思维,即模拟每次拿左边或右边,甚至还用DP来求解,但都无果。

看讨论区后还是很有启发,无论你当前这一步是拿左边还是右边,经过k轮之后的最终效果是,左边拿了连续的a的,右边拿了连续的k-a个。所以只需要对最终左边拿了几个进行DP建模,而无需模拟每一步是拿了左边还是右边。DP方法可看讨论区: https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/discuss/598111/Java-dp-solution(explanation-with-picture)

LeetCode Longest Common Subsequence

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000
  • The input strings consist of lowercase English characters only.

最长公共子序列问题,直接DP,完整代码如下:

class Solution {
public:
	int longestCommonSubsequence(string text1, string text2) {
		int m = text1.size(), n = text2.size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				int a = dp[i - 1][j], b = dp[i][j - 1], c = dp[i - 1][j - 1];
				if (text1[i - 1] == text2[j - 1])++c;
				dp[i][j] = max(max(a, b), c);
			}
		}
		return dp[m][n];
	}
};

本代码提交AC,用时92MS。

LeetCode Number of Ways to Paint N × 3 Grid

5383. Number of Ways to Paint N × 3 Grid

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: RedYellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are given n the number of rows of the grid.

Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:

Example 2:

Input: n = 2
Output: 54

Example 3:

Input: n = 3
Output: 246

Example 4:

Input: n = 7
Output: 106494

Example 5:

Input: n = 5000
Output: 30228214

Constraints:

  • n == grid.length
  • grid[i].length == 3
  • 1 <= n <= 5000

给定3种颜色,要求涂满N*3的网格,且相邻网格的颜色不能一样,问有多少种涂法。

首先,如果只有一行的话。如果涂3种颜色,则因为3种颜色各不相同,所以有3种排列的方法,共3!=6种。如果涂2种颜色,则相同的颜色涂两边,不同的颜色涂中间,首先从3种颜色中选2种,为$C_3^2$,2种颜色决定哪个放中间有2种方法,所以也有6种涂法。

对于涂3种颜色的一行,其下一行可以涂2种颜色,有2种涂法;也可以涂3种颜色,也有2种涂法。

对于涂2种颜色的一行,其下一行可以涂2种颜色,有3种涂法;也可以涂3种颜色,有2种涂法。

综合上面两种情况,下一行是2种颜色的情况=上一行是3种颜色*2+上一行是2种颜色*3,类似的,下一行是3种颜色的情况=上一行是3种颜色*2+上一行是2种颜色*2。根据递推公式,最终的情况数是两者相加,代码如下:

class Solution {
public:

	int numOfWays(int n) {
		if (n == 1)return 12;
		long long pre_two_colors = 6, pre_three_colors = 6;
		long long mod = 1e9 + 7;
		for (int i = 2; i <= n; ++i) {
			long long next_two_colors = 3 * pre_two_colors + 2 * pre_three_colors;
			long long next_three_colors = 2 * pre_two_colors + 2 * pre_three_colors;
			pre_two_colors = next_two_colors % mod;
			pre_three_colors = next_three_colors % mod;
		}
		return (pre_two_colors + pre_three_colors) % mod;
	}
};

本代码提交AC,用时0MS。

参考: