c++ - Iterative approach seems slower than recursive implemetation(coin change) -

the problem uva oj

my solution recursion

#include <cstdio>   using namespace std;  #define garbaze 0 //number of ways changes can made int coins[] = {garbaze,50,25,10,5,1}; //order not matter//as         in             //count_ways... function returning //0 if which_coin_now <= 0 //does n't matter have in index 0 [garbaze] .. must put //something there implement //code using 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 unsigned long long } return 0; } 

this 1 got accepted (and took 0.024 s)

and 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 second index @ num_of_coins , decrementing till 0 ...see pre calculating //we have start bottom up....if start @ dp[0][5] .....to dp[1][5] know need know //dp[1][4] , dp[..][5] before hand ..but have not calculated dp[1][4] yet...in case don't go infinite //loop or loop defined 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 iterative version not need initialize table working bottom - int n = 0; while(scanf("%d",&n)==1) {  printf("%llu\n",count_ways_change(n,5)); //llu unsigned long long  } return 0; } 

but got time limit exceeded one.it gives correct output don't see reason why 1 has slow?

the difference recursive solution remember partial solutions previous tasks (because dp table global , not removed between different inputs), while iterative doesn't - each new input, recalculates dp matrix scratch.

it can solved remembering portion of dp table calculated , avoid recalculating it, rather recalculate scratch every query.