Why we have to check weight[i-1] > j for the ith item ?
Why it should not be weight[i] > j as we are considering ith item not the i-1 th item.
Please clarify as I am having problem in understanding the indexing of dp array. I am not able to figure out when I need to take dp[n+1][m+1] and when I need dp[n][m].
as weight array indexing is start from 0
but in dp array we reserve 0 th row and column for 0 and infinity
so when we are at ith index in dp then actually we are at i-1 th index in array
so that is why we write weight[i-1]
and in dp we make it of size n+1 X m+1
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.