O(N*S) solution in C++ without taking pair<int,int> consideration


#1

int Solution::solve(const vector &A)
{
int n=A.size();
int capacity=0;
for(int i=0;i<n;i++)
capacity+=A[i];
capacity>>=1;
vector<vector>dp(n+1,vector(capacity+1,0));
for(int i=1;i<=capacity;i++)
dp[0][i]=INT_MAX;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=capacity;j++)
{
if(A[i-1]>j||dp[i-1][j-A[i-1]]==INT_MAX)
dp[i][j]=dp[i-1][j];
else
dp[i][j]=min((dp[i-1][j-A[i-1]])+1,dp[i-1][j]);
}
}
int k=capacity;
while(k>=0&&dp[n][k]==INT_MAX)
k–;
return dp[n][k];
}