题解 | #换钱的最少货币数#

题意：

给定一个整数数组和目标值
求用该数组的数构成目标值的最小数量。

方法一：

解题方法首先看起来像是贪心，但是因为给定的aim需要相等，所以可以使用动态规划，其存在的最优子结构如下：
- 一维数组dp[i]代表的是，aim为i的情况下的最少货币数，j是数组arr的索引。最初将dp[i] (i>0)初始化为INT_MAX-1
  (1) dp[i]=0 while i=0;
  (2) dp[i]=min(dp[i],dp[i-arr[j]]+1) while i>0;(其中使用dp[i-arr[j]]时保证i>=arr[j])
(1)式显然，(2)式表示的根据arr数组中的元素组成对dp数组的不断更新，初始化是INT_MAX-1，如果存在能组成dp[i]的方法，那么它是由dp[i-arr[j]]而递推得到的，由dp[i-arr[j]]增加一个arr[j]的货币即可，因此是更新为dp[i-arr[j]]+1。

由于题目限定了时间复杂度O(n*aim)，所以代码较为固定，即是对arr和dp的双重遍历，来不断更新dp数组，并得到最终结果dp[aim]。

代码如下：

class Solution {
public:
  /**
   * 最少货币数
   * @param arr int整型vector the array
   * @param aim int整型 the target
   * @return int整型
   */
  int minMoney(vector<int>& arr, int aim) {
      // write code here
      vector<int> dp(aim+1);
      //初始化dp数组
      dp[0]=0;
      //使用INT_MAX-1的目的是防止后面更新dp数组时有个加一，会整型溢出。
      for(int i=1;i<=aim;i++)
          dp[i]=INT_MAX-1;
      //双重循环，更新dp数组
      for(int j=0;j<arr.size();j++){
          for(int i=arr[j];i<=aim;i++){
              dp[i]=min(dp[i],dp[i-arr[j]]+1);
          }
      }
      if(dp[aim]==INT_MAX-1) 
          return -1;
      else 
          return dp[aim];
  }
};

图解如下：

复杂度分析：

时间复杂度： $O(n*aim)$ ，双重循环，外层 $O(n)$ ，内层 $O(aim)$ 。
空间复杂度： $O(n)$ ，一维数组dp， $O(n)$ 。