LeetCode 276 (Paint Fence)

Problem:

There is a fence with n posts, each post can be painted with one of the k colors.You have to paint all the posts such that no more than two adjacent fence posts have the same color. Return the total number of ways you can paint the fence.

Note:

n and k are non-negative integers.

解题思路：

分析：
由题目可以知道，最多有两个相邻的栅栏可以涂相同的颜色。

则主要思想是，如果前两根栅栏颜色相同，则第三根栅栏的颜色不能跟前两根的栅栏颜色相同，若是前两根栅栏颜色不同，则第三根栅栏颜色随便涂。综合的思想就是，第三根栅栏或者与第一根栅栏的颜色不同，或者与第二根的栅栏颜色不同。
（即，包括了，可以与前两个栅栏的颜色都不同，与第一根栅栏颜色不同时，可以与第二根相同，与第二根栅栏不同的时候可以与第一根相同）。

那么状态转移为：

N[i] = (K-1)*N[i-2]+(k-1)*N[i-1]
N[i]：第i根栅栏包括之前所有的可能颜色搭配

leetcode 256 (Paint House)

Problem：

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a n x 3
cost matrix. For example, costs[0][0]
is the cost of painting house 0 with color red; costs[1][2]
is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:

All costs are positive integers.

解题思路：

最初自己想的状态转移方程：

D[i][0] = V[i][0]+min{D[i-1][1]+D[i-1][2]}
D[i][1] = V[i][1]+min{D[i-1][0]+D[i-1][2]}
D[i][2] = V[i][2]+min{D[i-1][0]+D[i-1][1]}
return(min{D[i][0],D[i][1],D[i][2]})

代码如下：

public class AvoidRoads {
    public static void main(String args[]) {
        
        int[][] costs = {{1,2,4},{2,3,5},{3,4,7}};
        int[][] saveValue = new int[costs.length][3];
        int houseNum = costs.length - 1;//房子的个数
        System.out.println(Math.min(Math.min(minValue(houseNum,0,costs,saveValue),minValue(houseNum,1,costs,saveValue)),minValue(houseNum,2,costs,saveValue)));
    }
    public static int minValue(int houseNum,int houseColor,int[][] costs,int[][] saveValue){
        if(saveValue[houseNum][0]==1){
            return saveValue[houseNum][1];
        }else{
            int result;
            if(houseNum<= 0){
                result = Math.min(Math.min(costs[0][0], costs[0][1]), costs[0][2]);
            }else{
                result = costs[houseNum][houseColor]+Math.min(minValue(houseNum-1,(houseColor+1)%3,costs,saveValue),minValue(houseNum-1,(houseColor+2)%3,costs,saveValue));
            }
            saveValue[houseNum][0]=1;
            saveValue[houseNum][1]=result;
            return result;
        }
        
    }
}

然后看了大神写的代码思路如下：
大神使用了从前往后推的方法，而不是递归。这样也不用优化代码，即不需要用到saveValue了。
代码如下：

public class AvoidRoads {
    public static void main(String args[]) {
        int[][] costs = {{1,2,4},{2,3,5},{3,4,7}};
        if(costs==null || costs.length==0)System.out.println(0);
        int[] prevRow = costs[0];
         for(int i=1;i<costs.length;i++)
        {
            int[] currRow = new int[3];
            for(int j=0;j<3;j++)
                currRow[j]=costs[i][j]+Math.min(prevRow[(j+1)%3],prevRow[(j+2)%3]);
            prevRow = currRow;
        }
        System.out.println(Math.min(prevRow[0],Math.min(prevRow[1],prevRow[2])));
    }
}