See this
Consider an item having length (10^6 - 1) and cost c. Now if you required to form a stick with length 10^6, then the cost will be same as for length 2*(10^6 - 1) which is greater then 1.5 * 10^6 hence you should iterate to atleast 2 * 1.5 * 10^6 to cover all possible values.
1 Like
@vsp4 your assertion is very correct, it may be the case when an item and a stick have the lengths you mentioned, but my solution implicitly manage such a case as i am doing this using top-down approach rather than bottom-up . You might want to look at my solution i have linked to.
Moreover my main problem that why taking dp[12][1000005] is getting an Accepted is still a mystery to me. Can you throw some light on the same? Thank you.
1 Like