java - 3 栋房子和最低的油漆成本

Question

我正在解决这个问题

有一排房子，每间房子都可以涂上红、蓝、绿三种颜色。用某种颜色粉刷每间房子的成本是不同的。你必须粉刷所有的房子，这样相邻的两间房子就不会有相同的颜色。你必须以最低的成本粉刷房屋。你会怎么做？

import java.io.*;

import java.util.Scanner;
public class Solution { 
    static public int [][]v = new int[100][3];
    static public  int [][] dp = new int[100][3];

    public static void main(String args[] ) throws Exception {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 1; i <= n; ++i) {
            v[i][0] = in.nextInt();
        }
        for (int i = 1; i <= n; ++i) {
            v[i][1] = in.nextInt() ;
        }
        for (int i = 1; i <= n; ++i) {
            v[i][2] = in.nextInt();
        } 
        System.out.println( min_cost(n));
    }

    public static int min(int a, int b) {
        if (a <= b) {
            return a;
        }
        return b;
    }

    public static   int min(int a, int b, int c) {
        return min(min(a, b), c);
    } 

    public static int min_cost(int n) { 
        dp[1][0] = v[1][0];
        dp[1][1] = v[1][1];
        dp[1][2] = v[1][2];
        for (int i = 2; i <= n; ++i) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i][1];
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + v[i][2];
        }

        int result = min(dp[n][0], dp[n][1], dp[n][2]);
        return result;
    } 
}

我有一半的案例失败了......

Answer 1

你可以使用动态规划:

设 F(l,c) 是前 l 栋房子中最便宜的油漆，其中最后一间房子的颜色是 c设 w(k,c) 是将第 k 房子涂成 c

的成本

然后

F(0,c) = 0 对于所有 c 颜色

递归F:

F(k,c) = min( F(k-1,cc) + w(k,c) : cc in colors and cc!=c )

回答:

min( F(l,cc) : cc in colors)