题目：
思路：动态规划
-
状态：即栅栏的索引位置和 是否与上一个同色， 两种状态；
-
dp定义：
dp[i][0]指 第 i 个栅栏与第 i-1个栅栏同色的颜色可能性，dp[i][1]指第 i 个栅栏与上一个不同色的颜色可能性 -
选择：
此题没有求最大 或者 最小，而是列出所有的可能性！
根据题意，dp[i][0]即和上一个同色，由于同一个颜色只能相邻两次，那么第 i-1个栅栏注定不能和上一个（i-2）同色！ 所以dp[i][0]=dp[i-1][1]；
而dp[i][1]指 i 和 i-1不同色，那么 i-1位置的栅栏 既可以与i-2同色也可以与i-2不同色，且此时 i栅栏可以有 k-1种颜色可选； -
base case：
从 i=1 开始算，dp[1][0]=0 即第一次不可能和上次相同；
dp[1][1]=k 即第一次有k种可能性；
注意： 计算的是可能性的总和，所以结果是dp[n][0] + dp[n][1] ，而不是算的最大值or最小值；
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int k=in.nextInt();
if(k==1){
if(n>0 && n<=2){
System.out.println(1);
}else{
System.out.println(0);
}
}else {
// dp定义
int[][] dp = new int[n + 1][2];
// base case
// 0不算
dp[0][0] = 0;
dp[0][1] = 0;
// 第一个和前面相同的可能性0
dp[1][0] = 0;
// 第一个和前面不同的可能性k
dp[1][1] = k;
for (int i = 2; i <= n; i++) { // 遍历栅栏索引
// 和之前相同可能性1, 第i-1次只能是和上次不同
dp[i][0] = dp[i - 1][1];
// 和之前不同：要么第i-1此也不同 or 第i-1次与上次相同,然后再乘 k-1种可能性
dp[i][1] = (dp[i - 1][1] + dp[i - 1][0]) * (k - 1);
}
int r = dp[n][0] + dp[n][1];
System.out.println(r);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89199.html
