Iterative approach seems slower than recursive implemetation(coin change)

Question

The problem from uva OJ

my solution with recursion

#include <cstdio>


using namespace std;

#define garbaze 0
//number of ways changes can be made
int coins[] = {garbaze,50,25,10,5,1}; //order does not matter//as         in         the     //count_ways... function we are returning
//0 if which_coin_now is <= 0 so it
//does n't matter what we have in the index 0 [garbaze] .. but we must put //something there to implement the
//code using the pseudo code or recursive relation
typedef unsigned long long ull; //simple typedef
ull dp[7490][6]; //2d table
//recursive approach


ull count_ways_of_changes(int money_now,int which_coin_now)
{
    if(money_now == 0)
        return 1;
    if(money_now < 0 || which_coin_now <=0 )
        return 0;
    if(dp[money_now][which_coin_now] == -1)
        dp[money_now][which_coin_now] = count_ways_of_changes(money_now,which_coin_now-1) //excluding current coin
        + count_ways_of_changes(money_now - coins[which_coin_now],which_coin_now) ; //including current coin


    return dp[money_now][which_coin_now] ;


}

int main()
{
    for(int loop = 0; loop< 7490 ;loop++)
        for(int sec_loop = 0;sec_loop<6;sec_loop++)
                 dp[loop][sec_loop] = -1; //table initialization
int N = 0;
while(scanf("%d",&N)==1)
{
    printf("%llu\n",count_ways_of_changes(N,5)); //llu for unsigned long long
}
return 0;
}

This one got accepted (and took 0.024 s)

And my iterative approach :

#include <cstdio>
//#include <iostream>
//using namespace std;
typedef unsigned long long ull;
ull dp[7490][6];
#define garbaze 0
int value_coins[] = {garbaze,5,1,10,25,50} ;
inline ull count_ways_change(int money,int num_of_coins)
{
    for(int sum_money_now = 0; sum_money_now <= money ;sum_money_now++)
        for(int recent_coin_index = 0 ; recent_coin_index <= num_of_coins ; recent_coin_index++)
//common mistakes : starting the second index at num_of_coins and decrementing till 0 ...see we are pre calculating
//we have to start bottom to up....if we start at dp[0][5] .....to dp[1][5] but to know that i need to know
//dp[1][4] and dp[..][5] before hand ..but we have not calculated dp[1][4] yet...in this case i don't go to infinite
//loop or anything as the loop is well defined but i get stupid garbaze answer

    {
        if(sum_money_now == 0)
            dp[sum_money_now][recent_coin_index] = 1;
        else if(recent_coin_index == 0)
            dp[sum_money_now][recent_coin_index] = 0;
        else if(sum_money_now < value_coins[recent_coin_index] && recent_coin_index != 0)
            dp[sum_money_now][recent_coin_index] = dp[sum_money_now][recent_coin_index-1] ;
            else
                dp[sum_money_now][recent_coin_index] = dp[sum_money_now][recent_coin_index-1] + dp[sum_money_now - value_coins[recent_coin_index] ][recent_coin_index] ;
 //   cout<<dp[sum_money_now][recent_coin_index]<<endl;
    }


    return dp[money][num_of_coins] ;
}
int main()
{/*
    for(int loop = 0; loop< 7490 ;loop++)
        for(int sec_loop = 0;sec_loop<6;sec_loop++)
                 dp[loop][sec_loop] = -1; //table initialization

*/ //In the iterative version do not need to initialize the table as we are working bottom - up
int N = 0;
while(scanf("%d",&N)==1)
{

printf("%llu\n",count_ways_change(N,5)); //llu for unsigned long long

}
return 0;
}

But i got time limit exceeded for this one.It gives correct output but i don't see a reason why this one has to be so slow?

Answer 1

The difference is your recursive solution remember partial solutions from previous tasks (because the DP table is global and does not get removed between different inputs), while the iterative doesn't - for each new input, it recalculates the DP matrix from scratch.

It can be solved by remembering which portion of the DP table was already calculated and avoid recalculating it, rather than recalculate it from scratch for every query.