java涂色_【LeetCode（Java） - 276】栅栏涂色
【LeetCode(Java) - 276】栅栏涂色
【LeetCode(Java) - 276】栅栏涂色
文章目录
1、题目描述
2、解题思路
3、解题代码
1、题目描述
2、解题思路
??经典的动态规划问题
??定义 f[n] 表示 n 个栅栏时的总方案数。
??1、当 n 为 1 时，上色方案数为 f[1] = k；
??2、当 n 为 2 时，第 2 个栅栏的颜色可以和第 1 个一样，也可以不一样，因此总共有 f[2] = f[1] ×
k = k × k 个方案数；
??3、当 n > 3 时，给第 n 个栅栏上色时，有两种选择：
??3.1 和上一个不同颜色，那么此时第 n 个可以选的颜色有 k-1 个，截至到 n-1 的方案数为 f[n-1]，于是此时的方案总数为：f[n-1] × (k-1)
??3.2 和上一个相同颜色，那么上一个就不能和上上一个同色，第 n 个可以选的颜色有 k-1 个，第 n-1 个可以选的颜色只有一个，那就是和第 n 个一样的那个，因此截至 n-1 的方案数为 f[n-2] × 1，于是此时的方案总数为：f[n-2] × 1 × (k-1)；
??3.3 合计两个情况，给 n 个栅栏上色总共有 f[n] = f[n - 1] × (k - 1) + f[n - 2] × (k - 1)
3、解题代码
class Solution {
public int numWays(int n, int k) {
int[] f = new int[n+1]; // 方案数表，f[3] 表示给 3 个栅栏上色的方案数
for (int i = 1; i <= n; i++) {
if (i == 1) {
f[i] = k;
} else if (i == 2) {
f[i] = k * k;
} else {
// 第 n 个栅栏如果和上一个不同颜色，则有 f[i-1] * (k-1) 个方案数
// 第 n 个栅栏如果和上一个同颜色，那么上一个和前一个就不能同颜色，则有 f[i-2] * (k-1)
// 第 n 个栅栏上色方案数合计：f[i-1] * (k-1) + f[i-2] * (k-1)
f[i] = f[i - 1] * (k - 1) + f[i - 2] * (k - 1);
}
}
return f[n];
}
}
【LeetCode(Java) - 276】栅栏涂色相关教程
【LeetCode(Java) - 276】栅栏涂色 【LeetCode(Java) - 276】栅栏涂色 文章目录 1、题目描述 2、解题思路 3、解题代码 1、题目描述 2、解题思路 ??经典的动态规划问题 ??定义 f[n] 表示 n 个栅栏时的总方案数。 ??1、当 n 为 1 时，上色方案数为 f[1] = k； ??2、当 n 为 2 时，第 2 个栅栏的颜色可以和第 1 个一样，也可以不一样，因此总共有 f[2] = f[1] × k = k × k 个方案数； ??3、当 n > 3 时，给第 n 个栅栏上色时，有两种选择： ??3.1 和上一个不同颜色，那么此时第 n 个可以选的颜色有 k-1 个，截至到 n-1 的方案数为 f[n-1]，于是此时的方案总数为：f[n-1] × (k-1) ??3.2 和上一个相同颜色，那么上一个就不能和上上一个同色，第 n 个可以选的颜色有 k-1 个，第 n-1 个可以选的颜色只有一个，那就是和第 n 个一样的那个，因此截至 n-1 的方案数为 f[n-2] × 1，于是此时的方案总数为：f[n-2] × 1 × (k-1)； ??3.3 合计两个情况，给 n 个栅栏上色总共有 f[n] = f[n - 1] × (k - 1) + f[n - 2] × (k - 1) 3、解题代码 class Solution { public int numWays(int n, int k) { int[] f = new int[n+1]; // 方案数表，f[3] 表示给 3 个栅栏上色的方案数 for (int i = 1; i <= n; i++) { if (i == 1) { f[i] = k; } else if (i == 2) { f[i] = k * k; } else { // 第 n 个栅栏如果和上一个不同颜色，则有 f[i-1] * (k-1) 个方案数 // 第 n 个栅栏如果和上一个同颜色，那么上一个和前一个就不能同颜色，则有 f[i-2] * (k-1) // 第 n 个栅栏上色方案数合计：f[i-1] * (k-1) + f[i-2] * (k-1) f[i] = f[i - 1] * (k - 1) + f[i - 2] * (k - 1); } } return f[n]; } } 【LeetCode(Java) - 276】栅栏涂色相关教程