Li Kou daily question sword finger offer II 091. paint the house

The finger of the sword Offer II 091. Paint the house

A simple DP problem , But the data is too small , Feel that violence can be done , Although I didn't think about it

State shift ：
At present, the minimum price of painting a certain color is the price of the cheaper one of the other two colors plus the price of the current color
State transition equation ：
f[0][i] = Math.min(f[1][i-1], f[2][i-1]) + costs[i-1][0];
f[1][i] = Math.min(f[0][i-1], f[2][i-1]) + costs[i-1][1];
f[2][i] = Math.min(f[0][i-1], f[1][i-1]) + costs[i-1][2];

class Solution {
    
    public int minCost(int[][] costs) {
    
        int n = costs.length;
        int[][] f = new int[3][n+10];
        f[0][0] = f[1][0] = f[2][0] = 0;    
        for(int i = 1; i<=n; i++){
    
            f[0][i] = Math.min(f[1][i-1], f[2][i-1]) + costs[i-1][0];
            f[1][i] =  Math.min(f[0][i-1], f[2][i-1]) + costs[i-1][1];
            f[2][i] =  Math.min(f[0][i-1], f[1][i-1]) + costs[i-1][2];
        }
        int min = Math.min(f[0][n],f[1][n]);
        return Math.min(min,f[2][n]);
    }
}

• Time complexity O(n)
• Spatial complexity O(n)// Because only the previous value is needed , Dynamic arrays can be used to make the space complexity be O(1)

Dynamic array optimization

class Solution {
    
    int[][] f = new int[3][2];  
    void swap(){
    
        for(int i=0; i<3; i++){
    
            int tmp = f[i][0];
            f[i][0] = f[i][1];
            f[i][1] = tmp;
        }
    }
    public int minCost(int[][] costs) {
    
        int n = costs.length;
        
        f[0][0] = f[1][0] = f[2][0] = 0;    
        for(int i = 1; i<=n; i++){
    
            f[0][1] = Math.min(f[1][0], f[2][0]) + costs[i-1][0];
            f[1][1] =  Math.min(f[0]0], f[2][0]) + costs[i-1][1];
            f[2][1] =  Math.min(f[0][0], f[1][0]) + costs[i-1][2];
            swap();
        }
        int min = Math.min(f[0][0],f[1][0]);
        return Math.min(min,f[2][0]);
    }
}

• Time complexity O(n)
• Spatial complexity O(1)// But actually , Because there is less data , The effect of this method is not as good as the above