1. 就拿给定的例子来说,有5,2,3,三种面值的钱,现在拿出一张20元的,怎么兑换才能使钱的张数最少。
  2. 首先,我们知道可兑换的钱的最大张数是20,也就是面值是1的时候,其他可兑换的情况张数肯定小于20,那么可兑换张数<=20才是可考虑的范围,且要求最小值。
  3. 设置的计数数组的长度是比目标钱数还大1的,因为要记录从0到这个目标钱数可兑换的货币张数。
  4. 这个计数数组的初值均设为比给定钱数还大1,因为可能的最大值是aim,这里设为aim+1,就是为了后面可以更新min,毕竟只要能换,无论怎么换,张数都会比aim+1少。
  5. 先从小i开始讨论最少换多少张,因为换后面的大i也会用到前面的小i。就是说如果别人拿1,2,3,4,5,6,7,8,9,10来换,你只有面值2,3,5的,那么能不能换开,最少多少张就可以换开。
  6. 只有在面值比aim小的时候才可以换,换了一张之后,再看余下的钱能不能继续换,直到全部换开,换不开表示的话,dp值就保持初值,能换开就更新最小值
     int minMoney(int* arr, int arrLen, int aim ) {
       int max = aim + 1;   //假设最大值比给的目标值还大1
       int dp[max];  //建一个大小为max的数组,表示钱数为i时需要的最少货币张数
       for(int i = 0; i < max; i++)  //先假设钱数从0到max时均需要max张,后面再求最小值
           dp[i] = max;
       dp[0] = 0;   //显然,0元没有可兑换的
       for(int i = 1; i <= aim; i++){  //从1开始算钱数为i时最少需要兑换多少张
           for(int j = 0; j < arrLen; j++){  //怎么兑换就是看给定的数组中有没有面值更小的
               if(arr[j] <= i)   //给定货币的面值有更小的,或者相同的
                   dp[i] = min(dp[i], dp[i-arr[j]] +1);
                    //如果有更小的,那么先换一张,然后看余下的钱数还能不能换,依次类推如果能完全兑换,
                    //那么张数肯定比刚开始假设的max小,毕竟就算全换成1元的,张数也比max小
           }
       }
        return dp[aim] > aim ? -1 : dp[aim];  //要兑换aim的钱,张数最多就是aim张1元的情况,再多就错了,
    }