Q: Paint Houses - Algorithmic problems Here's a simple question from leetcode,
https://leetcode.com/problems/paint-house/description/
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.
Based on my understanding of the problem, here's my solution, which is verbose, but intentionally so,
import sys

class Solution(object):
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if costs is None or len(costs) == 0:
            return 0
        memo = [0 for _ in range(len(costs))]

        house, cost = self.get_min_cost_and_index(costs[0])
        memo[0] = cost
        for i in range(1, len(costs)):
            curr_house, curr_cost = self.get_min_cost_and_index(costs[i])
            if curr_house == house:
                mod_house, mod_cost = self.get_min_cost_and_index_minus_one(costs[i], house)
                memo[i] = memo[i-1] + mod_cost
                house = mod_house
            else:
                memo[i] = memo[i-1] + curr_cost
                house = curr_house

        return memo[-1]

    def get_min_cost_and_index(self, row):
        min_val, index = sys.maxsize, -1
        for i,v in enumerate(row):
            if v < min_val:
                min_val = v
                index = i
        return index, min_val

    def get_min_cost_and_index_minus_one(self, row, minus):
        min_val, index = sys.maxsize, -1
        for i, v in enumerate(row):
            if i == minus:
                continue
            if v < min_val:
                min_val = v
                index = i
        return index, min_val

The problem is on the test case below it fails,
if __name__ == '__main__':
    solution = Solution()
    print(solution.minCost([[5,8,6],[19,14,13],[7,5,12],[14,15,17],[3,20,10]]))

My solution gives 47 which is correct as per the logic I've implemented. The correct answer though is 43 and I can't how and why
Can someone help me what I'm missing out?

A: You can use dynamic programming to find the minimum cost of painting the first i houses, assuming house i is painted color j. Then the solution to the original problem is the color of the final house that results in the minimal total cost.
The dynamic program works, because (for example) the minimum cost of the first 10 houses painting the 10th house red is the cost of painting the 10th house red, plus the minimum total cost of painting the first 9 houses with the 9th house green or blue.
Here's a relatively terse program that implements this:
def lowcost(costs):
    c = [0, 0, 0]
    for cc in costs:
        c = [cc[j] + min(c[(j+k)%3] for k in [1, 2]) for j in xrange(3)]
    return min(c)

print(lowcost([[5,8,6],[19,14,13],[7,5,12],[14,15,17],[3,20,10]]))

It uses O(1) memory and O(N) time.

A: You're using a greedy approach that, as stated by j_random_hacker in the comments, won't find the optimal solution in all cases.
You might benefit from using a graph approach.
Imagine that each cell of the cost matrix is a Node. Each node, then, has edges connecting it to the two cells of different color from it from above and below.
That is: 
Cell cost[i][j] has edges connecting it to cost[i - 1][(j + 1)%3], cost[i - 1][(j + 2)%3], cost[i + 1][(j + 1)%3] and cost[i + 1][(j + 2)%3] for all i in [0, n-1] and j in [0, 2].
To simplify the next part, you can create two additional nodes with cost 0. One node (Start node) connected to all nodes in the first row and one node (End Node) connected to all nodes in the last row.
Now you just have to use Dijkstra's shortest path algorithm to calculate the shortest distance from Start Node to End Node.
