title: Iterative approach seems slower than recursive implemetation(coin change)
body: <p><a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=615" rel="nofollow">The problem from uva OJ</a></p>
  
  <p><a href="http://paste.ubuntu.com/11850485/" rel="nofollow">my solution with recursion</a></p>
  
  <pre><code>#include &lt;cstdio&gt;
  
  
  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 &lt;= 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 &lt; 0 || which_coin_now &lt;=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&lt; 7490 ;loop++)
          for(int sec_loop = 0;sec_loop&lt;6;sec_loop++)
                   dp[loop][sec_loop] = -1; //table initialization
  int N = 0;
  while(scanf("%d",&amp;N)==1)
  {
      printf("%llu\n",count_ways_of_changes(N,5)); //llu for unsigned long long
  }
  return 0;
  }
  </code></pre>
  
  <p>This one got accepted (and took 0.024 s)</p>
  
  <p>And my iterative approach :</p>
  
  <pre><code>#include &lt;cstdio&gt;
  //#include &lt;iostream&gt;
  //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 &lt;= money ;sum_money_now++)
          for(int recent_coin_index = 0 ; recent_coin_index &lt;= 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 &lt; value_coins[recent_coin_index] &amp;&amp; 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&lt;&lt;dp[sum_money_now][recent_coin_index]&lt;&lt;endl;
      }
  
  
      return dp[money][num_of_coins] ;
  }
  int main()
  {/*
      for(int loop = 0; loop&lt; 7490 ;loop++)
          for(int sec_loop = 0;sec_loop&lt;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",&amp;N)==1)
  {
  
  printf("%llu\n",count_ways_change(N,5)); //llu for unsigned long long
  
  }
  return 0;
  }
  </code></pre>
  
  <p>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?</p>