Buttom up approach

#1

I want to solve this problem using buttom up approah but i am unable to do that.

#2

hello @mkg825412gir

the implementation will be exactly same as knapsack.
follow this->
a) kmp to get all occurence
b) get product of all subsequence ,increment count for subsequence which gives zero remainder.
to optimise it we are using 2dp same as knapsack.

for(int i=1;i<=n;i++) {

for(int rem=0;rem<2520 ; rem++ ) {
    dp[i][rem]=dp[i-1][rem];//exclude
    dp[i][rem]+=dp[i][ (rem*current value)%2520];
   }

}
print dp[n][0]
#3

what should be base case for this approach?

#4

dp[i][0]=1

rest all entries must be zero

#5

It’s giving 128 output for given test case. please tell me what to do now?

#6

pls share ur code with me by saving it on cb ide

#7
#8

check now->

changed the base case.
becuase for empty set they are considering 1 as its product.
hence dp[0][1]=1;

#9

why dp[0][1]=1 only?

#10

dp[0][1]=1 ; means product of empty(0) subset is 1. so one way of doing this

#11

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.