I was solving this question on hackerearth -
I came through the recurrence relation
(doesn’t works correctly
if(dp[N][K] != -1)
return dp[N][K];
if(K == 0)
return 0;
if(K > N)
return 0;
if(N == K)
return 1;
else
{
dp[N-K][K] = solve(N-K,K); // Kth number is selected,problem reduced to subproblem with new sum as N - K
dp[N][K - 1] = solve(N,K - 1); // Kth number isn't selected,we need to explore upto (K - 1) now
dp[N][K] = dp[N-K][K] + dp[N][K - 1];
return dp[N][K];
}
instead of(works fine)
if(dp[N][K] != -1)
return dp[N][K];
if(K == 0)
return 0;
if(K > N)
return 0;
if(N == K)
return 1;
else
{
dp[N-K][K] = solve(N-K,K);
dp[N][K + 1] = solve(N,K + 1);
dp[N][K] = dp[N-K][K] + dp[N][K + 1];
return dp[N][K];
}
Whats the difference between 2 approaches for solving the above problem?