Find minimum number of coins that make a given value when use one coin only one by DP

#include<bits/stdc++.h>

#define INF 999999

using namespace std;

int c[50];                                       /// maximum coin number

int num[50][100000];                  /// number of coin count

int n;

int check(int i, int w)

{

    if(w < 0)

        return INF;

    if(i == n)

    {

        if(w == 0)

            return 0;

        return INF;

    }

    return num[i][w];

}

int cnt(int n, int target)

{

    for(int i=n-1; i>=0; i--)

    {

        for(int w=0; w<=target; w++)

        {

            int ans1 = 1 + check(i+1, w-c[i]);

            int ans2 = check(i+1, w);

            num[i][w] = min(ans1, ans2);

        }

    }

    return num[0][target];

}

int main()

{

    cout << "Enter Number of Coin :: ";

    cin >> n;

    cout << "Enter Coin :: ";

    for(int i=0; i<n; i++)

        cin >> c[i];

    int target;

    cout << "Enter Target Amount :: ";

    cin >> target;

    int r = cnt(n, target);

    if(r != INF)

        cout << "Minimum Number of Coin :: " <<  r << "\n";

    else

        cout << "Not Possible" << "\n";

    return 0;

}