C高速缓存动态编程

Question

我需要创建一个程序来计算变化，使用动态编程与缓存。该程序将返回一个包含硬币加起来的数组。

我已经咨询this page关于动态编程的伪代码，但输出只是硬币的数量，我不确定下面的行是否实际实现了缓存。

if ((values[j] <=a)&& (1+coins[a-values[j]]<coins[a])) 

以下是所有仍需修改的工作代码。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 


/** 
    @param amt value of change 
    @param values[] array of coin values 
    @param n number of available coins (length of values array) 
*/ 
float DynamicMakeChange(int amt,int values[],int n){ 
    int coins[amt]; //array of number of coins needed up to amt 
    coins[0]=0; 
    int a; //the current change to compute 

    // put number of coins in coins array at index a 
    for (a=1;a<=amt;a++){ 
     int array[a]; 
     int counter=0; 
     coins[a]=(int)INFINITY; 
     int j; 

     //loops all values of coins 
     for (j=0;j<n;j++){ 


      // if current coin value is smaller or equal than a (the current change value) 
      // and if the number of coins at the current amount-the currently looped value of a coin 
      // is less than the number of coins at the current amount. 
      if ((values[j] <=a)&& (1+coins[a-values[j]]<coins[a])){ 
       //array[counter++]=values[j]; 
       coins[a]=1+coins[a-values[j]]; 

      } 


     } 
    } 
    return coins[amt]; 

} 

int main() 
{ 
    int choice; 
    int array[] = { 1,2,5,10,20,50,100,200}; 
    printf("Please enter change to turn to coins:\n"); 
    scanf("%d",&choice); 
    int n= sizeof(array)/sizeof(array[0]); 
    float jasdkas=DynamicMakeChange(choice,array,n); 
    printf("Number of coins: %.0f",jasdkas); 
    return 0; 
} 

Answer 1

这一点，因为在你提供的资料应使用recursion解决的链接说明。您的解决方案不是递归的。你应该复发，例如自称。我不确定你需要返回什么，但如果它是在int数组中添加值，那么应该是这样的：

inside DynamicMakeChange(): 

if (n>0) 
return (array[n] + DynamicMakeChange(choice,array[n-1],n-1)); 
return 0;