在参加腾讯模拟考的时候其中嘚一道编程题是找零钱的问题,但是零钱的数量是一定的并不是无限的。而且零钱都是2的K次幂1,24,816,….每种零钱的数量是 2给定┅个数 n (
要枚举的动态规划的方法
后来采用优化的动态规划,发现结果不对
后来发现问题是因为零钱的数量是限制的,所以不能采用这种優化的方法只能通过枚举来实现动态规划,dp[i][j] = dp[i - 1][j] + dp[i][j-arr[i]]; 这个表达式中已经用了一次 arr[i],而你在用 dp[i][j-arr[i]]时这个方法中也会用掉
arr[i],所以就会造成结果出错的情況如果有无限的零钱的话,那就可以采用优化过的动态规划算法