A. Hit the Lottery


Can anyone do this by dp ??

The DP way would hit TLE as the constraints are too big. And to be honest its useless to use DP here when it can be done directly from Greedy, as the denominations are either a factor or multiple of each other.

Btw if you are still curious, here is the pseudocode for DP solution:

dp[0] = 0;
For i from 1 to N:
    dp[i] = 1 + dp[i-1];
    dp[i] = 1 + dp[i-5];
    dp[i] = 1 + dp[i-10];
    dp[i] = 1 + dp[i-20];
    dp[i] = 1 + dp[i-100];

Thank you :pray: