change my recursive solution into a dynamic programming solution

Question

here I am trying to convert my recursive solution into a dynamic solution but I am getting problem in converting. I am trying to count minimum possible coin to make value. what I am doing is I am taking all possible coin and putting inside a vector and finally in main function I will find and minimum of my vector and that will be my answer

int rec(vector<int>coins,int n,int sum,int counter)
{
     if(sum==0)
     {
         return 1;
     }
     if(n==0)
     {
         return 0;
     }
     int total=rec(coins,n-1,sum,counter);
     if(sum-coins[n-1]>=0)
     {
         total+=rec(coins,n,sum-coins[n-1],counter+1);
         if(sum-coins[n-1]==0)
         {
              vec.push_back(counter+1);
         }
     }
     return total;
}

Depending on the values of the coins, you won't need dynamic programming as the greedy choice suffices. — sweenish, May 29 '21 at 06:30

score 0 · Answer 1 · answered May 29 '21 at 05:58

you should first try to solve this type of problems by yourself.

BTW:

#define BIG 2147483647

int min_coin(int *coins, int m, int desire_value)
{
    int dp[desire_value+1];

    dp[0] = 0;
 
    for (int i=1; i<=desire_value; i++)
        dp[i] = BIG;
 
    for (int i=1; i<=desire_value; i++)
    {
        for (int j=0; j<m; j++)
          if (coins[j] <= i)
          {
              int diff = dp[i-coins[j]];
              if (diff != BIG && diff + 1 < dp[i])
                  dp[i] = diff + 1;
          }
    }
   
      if(dp[desire_value]==BIG)
        return -1;
   
    return dp[desire_value];
}

you can easily convert dp and coins to vector. vector is like array.(beware for allocate vector for dp you should reserve space in vector see here.)

thanks for your answer but I can do easily the solution you have provided...but my concern is too adjust counter in my dp solution — Belal Azam, May 29 '21 at 07:53

change my recursive solution into a dynamic programming solution

1 Answers1