322. 零钱兑换
状态 : d p [ i ] [ j ] dp[i][j] dp[i][j] 前i种货币拼成总面值为j的所需要的最少硬币数DP方程： d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c o i n s [ i ] + 1 ) dp[i][j] = min(dp[i-1][j],dp[i-1][j-coins[i]+1) dp[i][j]=min(dp[i−1][j],dp[i−1][j−coins[i]+1) 再用滚动数组优化一下空间。 class Solution { public: vector<int> dp; int MAX = 1e9; int coinChange(vector<int>& a, int m) { dp.resize(m+1,MAX); dp[0] = 0; for(int i=0;i<a.size();i++){ for(int j=a[i];j<=m;j++){ dp[j] = min(dp[j],dp[j-a[i]]+1); } } return dp[m]==MAX?-1:dp[m]; } };