序列型动态规划

public class Solution {
    /**
     * @param nums: the array
     * @return: the minimum times to flip digit
     */
    public int flipDigit(int[] nums) {
        // Write your code here
        
        if(nums==null || nums.length ==0){
            return 0;
        }
        
        int[][] f = new int[nums.length+1][2];
        
        f[0][0]=f[0][1]=0;
        
        for(int i=1;i<=nums.length;i++){
            for(int j=0;j<2;j++){
                f[i][j]= Integer.MAX_VALUE;
                int lastTurn = nums[i-1]==j?0:1;
                
                //k为i-1翻转后的最后一位
                for(int k=0;k<2;k++){
                    if(k==0 && j==1){
                        continue;
                    }
                    f[i][j] = Math.min(f[i][j],f[i-1][k]+lastTurn);
                }
            }
        }
        
        return Math.min(f[nums.length][0],f[nums.length][1]);
    }
}

public class Solution {
    /**
     * @param costs: n x k cost matrix
     * @return: an integer, the minimum cost to paint all houses
     */
    public int minCostII(int[][] costs) {
        // write your code here
        if(costs == null || costs.length == 0 || costs[0].length == 0){
            return 0;
        }
        
        
        int n = costs.length;
        int k = costs[0].length;
        int[][] f = new int[n][k];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<k;j++){
                f[i][j] = Integer.MAX_VALUE;
                if(i==0){
                    f[i][j] = costs[0][j];
                    continue;
                }
                
                for(int c=0;c<k;c++){
                    if(c==j){
                        continue;
                    }
                    
                    f[i][j]=Math.min(f[i-1][c]+costs[i][j],f[i][j]);
                }
            }
        }
        
        int res = Integer.MAX_VALUE;
        for(int i=0;i<k;i++){
            res = Math.min(f[n-1][i],res);
        }
        
        return res;
    }
}

public class Solution {
    /**
     * @param costs: n x k cost matrix
     * @return: an integer, the minimum cost to paint all houses
     */
    public int minCostII(int[][] costs) {
        // write your code here
        if(costs == null || costs.length == 0 || costs[0].length == 0){
            return 0;
        }
        
        
        int n = costs.length;
        int k = costs[0].length;
        int[][] f = new int[n][k];
        
        for(int j=0;j<k;j++){
            f[0][j] = costs[0][j];
        }   
        
        for(int i=1;i<n;i++){
            int preMinIndex = -1;
            int preSecMinIndex = -1;
            for(int j=0;j<k;j++){
                if(preMinIndex==-1 || f[i-1][j]<f[i-1][preMinIndex]){
                    preSecMinIndex = preMinIndex;
                    preMinIndex = j;
                }else if(preSecMinIndex==-1 || f[i-1][j]<f[i-1][preSecMinIndex]){
                    preSecMinIndex = j;
                }
            }
            
            for(int j=0;j<k;j++){
                if(j==preMinIndex){
                    f[i][j]= f[i-1][preSecMinIndex]+costs[i][j];
                }else{
                    f[i][j]= f[i-1][preMinIndex]+costs[i][j];
                }
            }
            
        }
        
        int res = Integer.MAX_VALUE;
        for(int i=0;i<k;i++){
            res = Math.min(f[n-1][i],res);
        }
        
        return res;
    }
}