零钱有限制和没有限制的找零钱问题

在参加腾讯模拟考的时候，其中的一道编程题是找零钱的问题，但是零钱的数量是一定的，并不是无限的。而且零钱都是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 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 temp(n+1, 0);

vector> 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]，所以就会造成结果出错的情况，如果有无限的零钱的话，那就可以采用优化过的动态规划算法。