java红蓝两种球,总共N个,N>2, 排列组合,连续3个颜色一样是非法的,求合法的排列数量
时间: 2023-08-15 15:03:47 浏览: 46
这道题可以用动态规划来解决。
我们设 $dp[i][0]$ 表示前 $i$ 个球中最后两个球颜色不同,且最后一个球是蓝色的合法排列数;$dp[i][1]$ 表示前 $i$ 个球中最后两个球颜色不同,且最后一个球是红色的合法排列数;$dp[i][2]$ 表示前 $i$ 个球中最后两个球颜色相同,且最后两个球都是蓝色的合法排列数;$dp[i][3]$ 表示前 $i$ 个球中最后两个球颜色相同,且最后两个球都是红色的合法排列数。
对于 $dp[i][0]$,它可以从 $dp[i-1][1]$ 和 $dp[i-1][3]$ 转移而来,即前一个球是红色或前两个球是红色的情况下最后一个球是蓝色。
对于 $dp[i][1]$,它可以从 $dp[i-1][0]$ 和 $dp[i-1][2]$ 转移而来,即前一个球是蓝色或前两个球是蓝色的情况下最后一个球是红色。
对于 $dp[i][2]$,它只能从 $dp[i-1][0]$ 转移而来,即前一个球是蓝色且上一个球是红色的情况下最后两个球都是蓝色。
对于 $dp[i][3]$,它只能从 $dp[i-1][1]$ 转移而来,即前一个球是红色且上一个球是蓝色的情况下最后两个球都是红色。
最终的答案为 $dp[N][0]+dp[N][1]$。
时间复杂度为 $O(N)$,空间复杂度为 $O(N)$。
以下是 Java 代码实现:
```java
public static long countValidPermutations(int n) {
long[][] dp = new long[n + 1][4];
dp[1][0] = dp[1][1] = 1;
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[i-1][1] + dp[i-1][3];
dp[i][1] = dp[i-1][0] + dp[i-1][2];
dp[i][2] = dp[i-1][0];
dp[i][3] = dp[i-1][1];
}
return dp[n][0] + dp[n][1];
}
```