兑换零钱(一)

脑筋急转弯，根本不考编程。

int minMoney(int* arr, int arrLen, int aim ) {
    int dp[5001], i, j, res;
    if(arrLen==0)
        return -1;
    if(aim==0)
        return 0;
    for(i=0; i<aim; i++) 
        dp[i] = aim+1;
    for(i=0; i<arrLen; i++) 
        dp[arr[i]-1] = 1;
    for(i=0; i<aim; i++) 
        for(j=0; j<arrLen; j++) 
            if(i>=arr[j]) 
                dp[i] = min(dp[i], dp[i-arr[j]]+1);
    return (dp[aim-1]<=aim ? dp[aim-1] : -1);
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @param aim int整型 the target
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int min(int a, int b){
    if(a>b)return b;
    else 
        return a;
}
int minMoney(int* arr, int arrLen, int aim ) {
    // write code here
    int dp[aim+1];
    dp[0]=0;
    for(int i=1; i<aim+1; i++){
        dp[i]=aim+1;
    }
    for(int i=1; i<aim+1; i++){
        for(int j=0; j<arrLen; j++){
            if(arr[j]<=i){
                dp[i]=min(dp[i],dp[i-arr[j]]+1);
            }
        }
    }
    if(dp[aim]>aim)
        return -1;
    else
        return dp[aim];
}

/**
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @param aim int整型 the target
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
int BubbleSort(int arrLen,int *dp,int target,int *arr){
    int res[100]={0},index=0;
    for(int i=0;i<arrLen;i++){
        if(target-arr[i]>=GetMinFaceValue(arr,arrLen)){  //比较的对象
            res[index++]=dp[target-arr[i]];
        }      
    }
    for(int i=0;i<index-1;i++){
        for(int j=0;j<index-i-1;j++){
            if(res[j]>res[j+1]){
                int temp=res[j];
                res[j]=res[j+1];
                res[j+1]=temp;
            }
        }
    }
    return res[0];
}

int GetMinFaceValue(int *arr,int arrLen){
    int min=arr[0];
    for(int i=1;i<arrLen;i++){
        if(arr[i]<min){
            min=arr[i];
        }
    } 
    return min;
}

int minMoney(int* arr, int arrLen, int aim ) {
    if(arrLen==0){
        return -1;
    }
    if(aim==0){
        return 0;
    }
    else if(aim>0&&aim<GetMinFaceValue(arr,arrLen)){
        return -1;
    }
    else{
        int dp[10000]={0},count=0;
        dp[0]=0;
        for(int i=0;i<arrLen;i++){
            dp[arr[i]]=1;
        } 
        for(int i=GetMinFaceValue(arr,arrLen);i<=aim;i++){
            if(dp[i]){
                continue;
            }
            else{
                dp[i]=BubbleSort(arrLen,dp,i,arr)+1;
            }
        }
        return dp[aim];
    }
}