LC 5604. Maximize Grid Happiness

link

class Solution {
public:
    int memo[5][5][7][7][1<<10];
    int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
        memset(memo,-1,sizeof(memo));
        return dfs(0,0,m,n,introvertsCount,extrovertsCount,0);
    }

    int dfs(int i, int j, int m, int n, int ins, int exs, int state){
        if(j==n){
            return dfs(i+1,0,m,n,ins,exs,state);
        }
        if(i==m || (ins==0 && exs==0)){
            return 0;
        }

        if(memo[i][j][ins][exs][state]!=-1) return memo[i][j][ins][exs][state];
        int res=dfs(i,j+1,m,n,ins,exs,state>>2);

        if(ins>0){
            int tmp=120;
            if(i>0 && state&1){
                tmp-=30;
                if(state&2){
                    tmp+=20;
                }else{
                    tmp-=30;
                }
            }
            if(j>0 && state&(1<<(2*(n-1)))){
                tmp-=30;
                if(state&(1<<(2*(n-1)+1))){
                    tmp+=20;
                }else{
                    tmp-=30;
                }
            }
            res=max(res,tmp+dfs(i,j+1,m,n,ins-1,exs,(state>>2)|(1<<2*(n-1)) ));
        }

        if(exs>0){
            int tmp=40;
            if(i>0 && state&1){
                tmp+=20;
                if(state&2){
                    tmp+=20;
                }else{
                    tmp-=30;
                }
            }
            if(j>0 && state&(1<<(2*(n-1)))){
                tmp+=20;
                if(state&(1<<(2*(n-1)+1))){
                    tmp+=20;
                }else{
                    tmp-=30;
                }
            }
            res=max(res,tmp+dfs(i,j+1,m,n,ins,exs-1,(state>>2)|(1<<2*(n-1))|(1<<(2*(n-1)+1) )));
        }
        return memo[i][j][ins][exs][state]=res;
    }
};