Minimum number of Coins-dynamic programming

Given a value N, total sum you have. You have to make change for Rs. N, and there is infinite supply of each of the denominations in Indian currency, i.e., you have infinite supply of { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000} valued coins/notes, Find the minimum number of coins and/or notes needed to make the change for Rs N.

The first line of input contains an integer T denoting the number of test cases. Each test case consist of an Integer value N denoting the amount to get change for.


Print all the denominations needed to make the change in a separate line.

Example:
Input:
1
43

Output:
20 20 2 1

Explanation:
Testcase 1: Sum of Rs 43 can be changed with minimum of 4 coins/ notes 20, 20, 2, 1.

first method:
easy just using if else:
c++ implementation:
t is the no. of test cases:

#include <iostream>
using namespace std;

int main() {
 int x;cin>>x;
 while(x--){
    int n;
    cin>>n;
    while(n){
        if(n>2000){cout<<"2000 ";n-=2000;}
        else if(n>=500){cout<<"500 ";n-=500;}
        else if(n>=200){cout<<"200 ";n-=200;}
        else if(n>=100){cout<<"100 ";n-=100;}
        else if(n>=50){cout<<"50 ";n-=50;}
        else if(n>=20){cout<<"20 ";n-=20;}
        else if(n>=10){cout<<"10 ";n-=10;}
        else if(n>=5){cout<<"5 ";n-=5;}
        else if(n>=2){cout<<"2 ";n-=2;}
        else if(n>=1){cout<<"1 ";n-=1;}
    }
    cout<<endl;
 }
 return 0;
}

method 2:
dynamic programming:
c++ implementation:
t is the no. of test cases:

#include<bits/stdc++.h>
using namespace std;
int coins[]={1,2,5,10,20,50,100,200,500,2000};
void change(int n)
{
    int i,dp[10][n+1],j;
    for(i=0;i<=n;i++)
    {
        dp[0][i]=i;
    }
    for(i=1;i<10;i++)
    {
        for(j=0;j<=n;j++)
        {
            if(j>=coins[i])
            dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1);
            else
            dp[i][j]=dp[i-1][j];
        }
    }
     i=9;j=n;
    while(i>=0 && j>0)
    {
        if(dp[i][j]==dp[i-1][j])
        i=i-1;
        else
        {
            cout<<coins[i]<<" ";
            j=j-coins[i];
        }
    }
    
}
int main()
 {
 //code
 int t,n;
 cin>>t;
 for(int i=0;i<t;i++)
 {
     cin>>n;
     change(n);
     cout<<endl;
 }
 return 0;
}