Paint House - Many Colors

1. You are given a number n and a number k separated by a space, representing the number of houses and number of colors.

2. In the next n rows, you are given k space separated numbers representing the cost of painting nth house with one of the k colors.

3. You are required to calculate and print the minimum cost of painting all houses without painting any consecutive house with same color.

Input Format

A number n

n1-0th n1-1st n1-2nd .. n1-kth

n2-0th n2-1st n2-2nd .. n2-kth

.. n number of elements

Output Format

A number representing the minimum cost of painting all houses without painting any consecutive house with same color.

Constraints

1 <= n <= 1000

1 <= k <= 10

0 <= n1-0th, n1-1st, .. <= 1000

Sample Input

4 3

1 5 7

5 8 4

3 2 9

1 2 4

Sample Output

8

Solution

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {

        // input

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), m = sc.nextInt();

        int[][] A = new int[n][m];

        

        for(int i=0;i<n;i++)

            for(int j=0;j<m;j++)

                A[i][j] = sc.nextInt();

        

        int color[] = new int[m];

        

        for(int i=0;i<n;i++){

            int col[] = new int[m];

            for(int j=0;j<m;j++){

                int min = Integer.MAX_VALUE;

                for(int c=1;c<m;c++){

                    min = Math.min(min,color[(j+c)%m]);

                }

                col[j] = A[i][j] + min;

            }

            color = col;

        }

        

        int min = color[0];

        for(int c=1;c<m;c++)

            min = Math.min(min,color[c]);

        System.out.println(min);

    }

}