There are n consecutives houses in the city. You are painting n houses with k different colors. You must paint the house following these rules:\n\n* Every house must be painted with exactly one color.\n* There cannot be three or more consecutive houses with the same color.\n\n\n\nGiven the two integers n and k, return the number of ways you can paint the houses.\n\nExample:\n\nInput: n = 3, k = 2\nOutput: 6\n\nExplaination: Possible ways to paint the houses with 2 colors(0, and 1) are : 1 1 0, 1 0 1, 1 0 0, 0 1 1, 0 0 1, 0 1 0\n\nNeed help around this problem, I mean how to approach this kind of problem, is it through DP, graph, or maths?

There are n consecutives houses in the city. You are painting n houses with k different colors. You must paint the house following these rules:\n\n Every house 