往年试卷上的一题,我只会用贪心法做,不知道如何用动态规划做.不知道怎么写出他的递推公式.感觉不好用动态规划做.还是请教一下大伙吧

// if (x == 面值一种) return 1;
// else MinCoin = 1 +MinCoin(x-比x小的面值);

#include <iostream>
using namespace std;

int MinCoin(const int * coin_value,int n,int Xleft){
    for (int i = 0;i < n; i++)
        if (Xleft == coin_value[i])
            return 1;
    for ( i = 0 ; i < n && coin_value[i] < Xleft;i++);
    int *num_coin = new int [i];
    int mincoin;
    for (int j = 0;j < i;j++){
        num_coin[j] = 1 + MinCoin(coin_value,i,Xleft - coin_value[j]);
        if (j == 0)
            mincoin = num_coin[0];
        else 
            mincoin = mincoin > num_coin[j] ? num_coin[j] : mincoin;
    }
    delete num_coin;
    return mincoin;
}
int main()
{
    int N;
    cin>>N;
    int * coin_value = new int [N];
    for (int i = N - 1;i >= 0;i--)
        cin>>coin_value[i];
    int X;
    cin>>X;
    cout<<MinCoin(coin_value,N,X)<<endl;
    delete coin_value;
    return 0;
}

郁闷.今天考试还是这个题,不过要用回溯法做...时间那么短 题目那么多
哪里做的出啊?bt

算法描述:
要求最少的数量:去f(num-c1),f(num-c2).....;.得最少的并且要储存,把递归的结果保存,就行了