title: minimum coin with no DP
body: <pre><code>public int MinCoins(int[] change, int cents)
  {
      Stopwatch sw = Stopwatch.StartNew();
  
      int coins = 0;
      int cent = 0;
      int finalCount = cents;
      for (int i = change.Length - 1; i &gt;= 0; i--)
      {
          cent = cents;
  
          for (int j = i; j &lt;= change.Length - 1; j++)
          {
              coins += cent / change[j];
              cent = cent % change[j];
              if (cent == 0) break;
          }
  
          if (coins &lt; finalCount)
          {
              finalCount = coins;
          }
          coins = 0;
      }
      sw.Stop();
      var elapsedMs = sw.Elapsed.ToString(); ;
      Console.WriteLine("time for non dp " + elapsedMs);
      return finalCount;
  }
  
  public  int MinCoinsDp(int[] change, int cents)
  {
      Stopwatch sw = Stopwatch.StartNew();
      int[] minCoins = new int[cents + 1];
  
      for (int i = 1; i &lt;= cents; i++)
      {
          minCoins[i] = 99999;
  
          for (int j = 0; j &lt; change.Length; j++)
          {
  
              if(i &gt;= change[j])
              {
  
                  int n = minCoins[i - change[j]] + 1;
  
                  if (n &lt; minCoins[i])
                      minCoins[i] = n;
              }
          }
      }
      sw.Stop();
      var elapsedMs = sw.Elapsed.ToString();
      Console.WriteLine("time for dp " + elapsedMs);
  
      return minCoins[cents];
  }
  </code></pre>
  
  <p>I have written a minimum number of coins programs using iterative and Dynamic Programming. I have seen a lot of blogs discussing about DP for this problem. Iterative solutions has running time O(numberOfCoins * numberofCoins) and DP has O(numberofcoins*arraySize) roughly same. Which one is better? Please suggest good book for advanced algorithms.</p>
  
  <p>Please run with {v1 > v2 > v3 > v4} like {25,10,5}</p>