class Solution { public: /** * 最少货币数 * @param arr int整型vector the array * @param aim int整型 the target * @return int整型 */ int minMoney(vector& arr, int aim) { // write code here //要求返回最少货币数 //对写出来的暴力尝试进行动态规划 int n=arr.size(); int dp[10001][5001]; for(int i=0;i<=n;i++) dp[i][0]=0;//把第一列全都初始化为0 for(int i=1;i<=aim;i++) dp[n][i]=-1;//把最后一行除了第一个元素以外的值都赋值为-1 //下面找一个普通位置的依赖关系 //由分析知道应该从倒数第二行第一列开始逐渐向上填表 for(int i=n-1;i>=0;i--){ for(int j=1;j<=aim;j++) { int select_1=(j-arr[i])>=0?dp[i][j-arr[i]]:-1; int select_2=dp[i+1][j]; if(select_1==select_2&&select_1==-1)//说明两种方案都是无效的，说明怎么都凑不出来这么多钱 { dp[i][j]=-1; } else if(select_1==-1||select_2==-1){//如果其中之一为-1，返回那个不是-1的 if(select_1==-1){ dp[i][j]=select_2; } else{ dp[i][j]=select_1+1;//因为第一种情况选了当前纸币所以数量还要+1 } } //两个方案都不是-1则跳出货币数最少的那一个 else{ dp[i][j]=min(select_1+1,select_2); } } } return dp[0][aim]; } };