Dynamic Programming in O(N^3)

Problem is this one: https://leetcode.com/problems/paint-house/

Easy

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.

Example:

Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. 
             Minimum cost: 2 + 5 + 3 = 10.

Accepted

78,373

Submissions

152,619

It smells like a DP, so it must be DP. What can be done is the following:
a) Create a copy of the input called "dp"
b) For each row r starting from the second row
    c) For each col i
        d) Find the Min among all the columns in row r-1 that are diff than i
        e) Assign this Min to d[r][i]
f) Your solution will be the very Min in the last row

That's it. Code is down below, cheers, ACC.

public class Solution
{
    public int MinCost(int[][] costs)
    {
        if (costs.Length == 0) return 0;

        int[][] dp = (int[][])costs.Clone();

        for (int i = 1; i < dp.Length; i++)
        {
            for (int k = 0; k < dp[0].Length; k++)
            {
                int minPrior = Int32.MaxValue;
                for (int j = 0; j < dp[0].Length; j++)
                {
                    if (k != j) minPrior = Math.Min(minPrior, dp[i - 1][j]);
                }
                dp[i][k] += minPrior;
            }
        }

        int min = Int32.MaxValue;
        for (int i = 0; i < dp[0].Length; i++) min = Math.Min(min, dp[dp.Length - 1][i]);

        return min;
    }
}