unsigned long long solution2(int deep, int* coinNum, int* coinValue,int* coinSum,vector<vector<int>>& dp, int sum) { if (deep == 6) return sum > coinNum[deep] ? 0 : 1; if (dp[deep][sum] > 0 || sum > coinSum[deep]) return dp[deep][sum]; int ans = 0; for (int i = 0; i <= min(sum / coinValue[deep], coinNum[deep]); ++i)  ans += solution2(deep + 1, coinNum, coinValue, coinSum, dp, sum - i*coinValue[deep]); dp[deep][sum] = ans; return ans; } unsigned long long solution3(int deep, int* coinNum, int* coinValue,int * coinSum, vector<vector<int>>& dp, int m) { int ans = 0; for (int i = 0; i <= m; ++i) { if (0 == dp[deep][i])  continue; for (int j = min(i / coinValue[deep], coinNum[deep]); j >= 0; --j) { if (i - j*coinValue[deep] > coinSum[deep + 1]) break; if (deep < 5)  dp[deep + 1][i - j*coinValue[deep]] += dp[deep][i]; else  ans += dp[deep][i]; } } return deep < 5 ? solution3(deep + 1, coinNum, coinValue, coinSum, dp, m) : ans; } int main() { int m = 5000; vector<vector<int>> dp(7, vector<int>(m+1, 0)); int coinValue[7] = { 100,50,20,10,5,2,1 };               //七种硬币面值 int coinNum[7] = { 1000,1000,1000,1000,1000,1000,1000 }; //七种硬币数量 //coinSum[i]表示在index在i-1以后的所有硬币能够凑起来的最大数，比如本例中coinSum[6]=1000,coinSum[5]=3000 int coinSum[7];                              coinSum[6] = coinNum[6] * coinValue[6]; for (int i = 5; i >= 0; --i) coinSum[i] = coinSum[i + 1] + coinNum[i] * coinValue[i]; cout  << solution2(0, coinNum, coinValue, coinSum, dp, m) << endl; vector<vector<int>> dp1(7, vector<int>(m + 1, 0)); dp1[0][m] = 1; cout  << solution3(0, coinNum, coinValue, coinSum, dp1, m) <<  endl;    return 0; }