LeetCode 276：栅栏涂色

题目：

思路：动态规划

• 状态：即栅栏的索引位置和 是否与上一个同色， 两种状态；

• 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);
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36