Top Down - Memoization

interview-questions
amazon
Tags: #<Tag:0x00007f24217aa098> #<Tag:0x00007f24217a9f30>

#1
int helper(vector<vector<int>> &A, int index, int color, int N, int C, vector<vector<int>> &Dp)
{
    if (index == N)
        return 0;
    if (Dp[index][color] != -1)
        return Dp[index][color];
    int ans = A[index][color];
    int temp = INT_MAX;
    for (int i = 0; i < C; i++)
    {
        if (i != color)
        {
            temp = min(temp, helper(A, index + 1, i, N, C, Dp));
        }
    }
    Dp[index][color] = ans + temp;
    return Dp[index][color];
}

int Solution::solve(vector<vector<int> > &A) {
    int N = A.size();
    vector<vector<int> > Dp(N+1,vector<int>(3,-1));
    return min(helper(A, 0, 0, N, 3, Dp), min(helper(A, 0, 1, N, 3, Dp), helper(A, 0, 2, N, 3, Dp)));
}