Can someone suggest a better approach to this DP Question!

general
1

Hi I just solved a question

C - Tak and Cards

I had to use 3D Dynamic Programming in it.
So my question is…

Is it possible to solve it using 2D Dp?

Here is my solution, i used a Top Down approach + memo, it passed all tests.

#include <bits/stdc++.h>
#define N 55

using namespace std;

int num[N];
int dp[N][N][N*N];

int solve(int i,int d,int sum,int n){

	if(sum==0 && d==0){
		return 1;
	}

	if(i>=n || d==0){
		return 0;
	}

	if(dp[i][d][sum]!=-1)
    {
		return dp[i][d][sum];
	}
	int pos1=solve(i+1,d-1,sum-num[i],n);
	int pos2=solve(i+1,d,sum,n);

	dp[i][d][sum]=pos2+pos1;
	return pos1+pos2;
}

int main(){

    for(int i=0;i<N;i++)
    {
    	for(int j=0;j<N;j++)
        {
    		for(int k=0;k<N*N;k++)
            {
    			dp[i][j][k]=-1;
    		}
    	}
    }

	int n,a;
    cin>>n>>a;
	for(int i=0;i<n;i++)
    {
        cin>>num[i];
    }

	int res=0;

	for(int i=1;i<=n;i++)
    {
		res+=(solve(0,i,i*a,n));
	}

	cout<<res<<endl;

	return 0;
}
1 Like