想做淘宝 网站怎么做,大型平台网站开发,徐州cms模板建站,最专业的网站建设seo优化服务公司有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏#xff0c;每个栅栏柱可以用其中一种颜色进行上色。
你需要给所有栅栏柱上色#xff0c;并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后#xff0c;返回所有有效涂色的方案数。
注意: n 和 k 均为非负的整数。
示例…有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏每个栅栏柱可以用其中一种颜色进行上色。
你需要给所有栅栏柱上色并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后返回所有有效涂色的方案数。
注意: n 和 k 均为非负的整数。
示例:
输入: n 3k 2 输出: 6 解析: 用 c1 表示颜色 1c2 表示颜色 2所有可能的涂色方案有: 柱 1 柱 2 柱 3 ----- ----- ----- ----- 1 c1 c1 c2 2 c1 c2 c1 3 c1 c2 c2 4 c2 c1 c1 5 c2 c1 c2 6 c2 c2 c1
思路动态规划。
n1,k钟
n2,k*k种。
n2:
n可以和n-1位置颜色相同这时这两个位置可选项有k-1种颜色可用再乘n-2位置方案总数。
n可以和n-1位置颜色不同这时这个位置有k-1种颜色可用再乘n-1位置的方案总数。
class Solution {public int numWays(int n, int k) {if(n0)return 0;if(n1)return k;int[] arrnew int[n];arr[0]k;arr[1]k*k;for(int i2;in;i){arr[i](arr[i-1]arr[i-2])*(k-1);}return arr[n-1];}
}
