下面代码采用动态规划求解零钱兑换问题：给定 种硬币，第𝑖种硬币的面值为𝑐𝑜𝑖𝑛𝑠[𝑖 − 1]，目标金额为
𝑎𝑚𝑡，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回-1。
int coinChangeDPComp(vector<int> &coins, int amt) { int n = coins.size(); int MAX = amt + 1; vector<int> dp(amt + 1, MAX); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int a = 1; a <= amt; a++) { if (coins[i - 1] > a) dp[a] = dp[a]; else dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1); } } return dp[amt] != MAX ? dp[amt] : -1;}