Simple Recursion+Memorisation in C++


#1
int dp[100007][3]; // dp[i][j] represents the min ans when jth color is not used for the ith house
int find(vector<vector<int> > & A,int n,int color)
{
    if(n==-1) return 0;
    if(dp[n][color]!=-1) return dp[n][color];
    int currans = INT_MAX;
    for(int i=0;i<3;i++)
    {
        if(i==color) continue;
        int x = find(A,n-1,i);
        currans = min(currans,x+A[n][i]);
    }
    return dp[n][color] = currans ;
}
int Solution::solve(vector<vector<int> > &A) {
 memset(dp,-1,sizeof(dp));
 int n=A.size();
 return min(find(A,n-1,0),min(find(A,n-1,1),find(A,n-1,2)));
}