在参加腾讯模拟考的时候，其中的一道编程题是找零钱的问题，但是零钱的数量是一定的，并不是无限的。而且零钱都是2的K次幂，1，2，4，8，16，….每种零钱的数量是 2，给定一个数 n (

int k_count = 0;long long  k_sum = 1;while (k_sum < n)           //小于且最接近n的2的K次幂的整数{k_sum = k_sum * 2;k_count++;}vector<long long > arr(k_count, 0);   //把相应的零钱存入数组中k_sum = 1;arr[0] = 1;for (int i = 1; i < k_count; ++i){k_sum *= 2;arr[i] = k_sum;}

要枚举的动态规划的方法

vector<long long> temp(n+1, 0);vector<vector<long long>>  dp(k_count, temp);for (int i = 0; i < k_count; ++i)dp[i][0] = 1;dp[0][1] = 1;        //因为每种零钱的数量只有两张dp[0][2] = 1;for (int i = 1; i < k_count; ++i){for (int j = 1; j <= n; ++j){if (j < arr[i])                  //如果总的钱数，小于当前的零钱dp[i][j] = dp[i - 1][j];else{int count = 0;for (int k = 0; arr[i] * k <= j && k < 3; ++k)     //计算用 k 张arr[i] 的零钱的时候，用多少张找零的方式count += dp[i - 1][j-arr[i]*k];dp[i][j] = count;}}}

后来采用优化的动态规划，发现结果不对

for (int i = 1; i < k_count; ++i){for (int j = 1; j <= n; ++j){if (j < arr[i])                  //如果总的钱数，小于当前的零钱dp[i][j] = dp[i - 1][j];else{               dp[i][j] = dp[i - 1][j] + dp[i][j-arr[i]];      //在每张零钱的张数限制的条件下时不能采用这种优化的方法}}}

后来发现问题是，因为零钱的数量是限制的，所以不能采用这种优化的方法，只能通过枚举来实现动态规划，dp[i][j] = dp[i - 1][j] + dp[i][j-arr[i]]; 这个表达式中已经用了一次 arr[i],而你在用 dp[i][j-arr[i]]时，这个方法中也会用掉 arr[i]，所以就会造成结果出错的情况，如果有无限的零钱的话，那就可以采用优化过的动态规划算法。