Java动态规划之硬币找零问题实现代码
动态规划的基本思想是将待求解问题分解成若干个子问题,先求解子问题,并将这些子问题的解保存起来,如果以后在求解较大子问题的时候需要用到这些子问题的解,就可以直接取出这些已经计算过的解而免去重复运算。保存子问题的解可以使用填表方式,例如保存在数组中。 用一个实际例子来体现动态规划的算法思想――硬币找零问题。 问题描述: 假设有几种硬币,并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。例如几种硬币为[1,3,5],面值2的最少硬币数为2(1,1),面值4的最少硬币数为2(1,3),面值11的最少硬币数为3(5,5,1或者5,3). 问题分析: 假设不同的几组硬币为数组coin[0,...,n-1]. 则求面值k的最少硬币数count(k),那么count函数和硬币数组coin满足这样一个条件: count(k) = min(count(k - coin[0]),count(k - coin[n - 1])) + 1; 所以我们可以创建一个矩阵matrix[k + 1][coin.length + 1],使matrix[0][j]全部初始化为0值,而在matrix[i][coin.length]保存面值为i的最少硬币数. 而且具体的过程如下: * k|coin 1 3 5 min * 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 0 2 * 3 3 1 0 3,1 * 4 2 2 0 2,2 * 5 3 3 1 3,1 * 6 2 2 2 2,2,2 * ... 最后,具体的Java代码实现如下: public static int backTrackingCoin(int[] coins,int k) {//回溯法+动态规划 if (coins == null || coins.length == 0 || k < 1) { return 0; } int[][] matrix = new int[k + 1][coins.length + 1]; for (int i = 1; i <= k; i++) { for (int j = 0; j < coins.length; j++) { int preK = i - coins[j]; if (preK > -1) {//只有在不小于0时,preK才能存在于数组matrix中,才能够进行回溯. matrix[i][j] = matrix[preK][coins.length] + 1;//面值i在进行回溯 if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//如果当前的硬币数目是最少的,更新min列的最少硬币数目 matrix[i][coins.length] = matrix[i][j]; } } } } return matrix[k][coins.length]; } 代码经过测试,题目给出的测试用例全部通过! 总结 以上就是本文关于Java动态规划之硬币找零问题实现代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题。如有不足之处,欢迎留言指出。感谢朋友们对本站的支持! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |