class Solution {
public:
    int dp[52][100002];
    int numWays(int n, int k) {
        memset(dp, -1, sizeof(dp));

        int answer = call(0, 0, false, n, k);

        return answer;
    }

    int call(int post, int color, bool isSameColor, int n, int k)
    {
        if(post == n)
            return 1;

        if(dp[post][color] != -1)
            return dp[post][color];

        int result = 0;
        for(int i = 1; i <= k; i++)
        {
            if(color == i && isSameColor)
            {
                continue;
            }
            else if(color == i)
            {
                result += call(post + 1, i, true, n, k);
            }
            else
            {
                result += call(post + 1, i, false, n, k);
            }
        }

        return dp[post][color] = result;
    }
};