jain12

Coin change problem by DP

Jun 7th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int Count(int arr[],int n,int value){
  5.   int total[n+1][value+1];
  6.   for(int i=0;i<=n;i++)
  7.     total[i][0]=1;
  8.   for(int i=0;i<=value;i++)
  9.     total[0][i]=0;
  10.   for(int i=1;i<=n;i++){
  11.     for(int j=1;j<=value;j++){
  12.            if(arr[i-1]<=j)
  13.              total[i][j]=total[i][j-arr[i-1]]+total[i-1][j];
  14.            else
  15.             total[i][j]=total[i-1][j];
  16.       }
  17.     }
  18.     return total[n][value];
  19.   }
  20.  
  21. int main(){
  22.   int arr[] = {2,5,3,6};
  23.   int m = sizeof(arr)/sizeof(arr[0]);
  24.   cout<< Count(arr, m, 10);
  25.   return 0;
  26.   }
Add Comment
Please, Sign In to add comment