LC: 256. Paint House - spiralgo/algorithms GitHub Wiki

Paint House

The Essence:

• It's should be fairly obvious that choosing the local optimum doesn't always result in the global optimum. (consider: houses = [1, 9, 18], [1, 999, 999](/spiralgo/algorithms/wiki/1,-9,-18],-[1,-999,-999) )
• Trying to choose one of the 3 colors in each house would lead to decision tree and time complexity approximately of size 2^n.
• One can notice that the decision made for a house, carries it value to the second house: houses = [1, 9, 18], [1, 999, 999](/spiralgo/algorithms/wiki/1,-9,-18],-[1,-999,-999) is equivalent to houses = [1+9(previous 2. min), 999+1, 999+1](/spiralgo/algorithms/wiki/1+9(previous-2.-min),-999+1,-999+1). This structure can accumulate from the first house to the last or from the last to the first. Either way, not only solving individual problems but also combining them optimally can solve the global problem.

Details:

The process here can be implemented using for loops and accumulating the value on the input matrix. The return value is simply the minimum in the last row of the grid.

Actually, this process of solving some previous problems, then optimally using the previous solutions to solve the next problems is called dynamic programming. It has has many crucial application whether it be in theoretical or applied informatics.