Java动态规划之硬币找零问题实现代码
动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，并将这些子问题的解保存起来，如果以后在求解较大子问题的时候需要用到这些子问题的解，就可以直接取出这些已经计算过的解而免去重复运算。保存子问题的解可以使用填表方式，例如保存在数组中。
用一个实际例子来体现动态规划的算法思想——硬币找零问题。
问题描述:
假设有几种硬币，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。例如几种硬币为[1,3,5],面值2的最少硬币数为2(1,1),面值4的最少硬币数为2(1,3),面值11的最少硬币数为3(5,5,1或者5,3,3).
问题分析:
假设不同的几组硬币为数组coin[0,...,n-1].则求面值k的最少硬币数count(k),那么count函数和硬币数组coin满足这样一个条件:
count(k)=min(count(k-coin[0]),...,count(k-coin[n-1]))+1;
并且在符合条件k-coin[i]>=0&&k-coin[i]
所以我们可以创建一个矩阵matrix[k+1][coin.length+1],使matrix[0][j]全部初始化为0值,而在matrix[i][coin.length]保存面值为i的最少硬币数.
而且具体的过程如下:
*k|coin135min *00000 *11001 *22002 *33103,1 *42202,2 *53313,3,1 *62222,2,2 *...
最后,具体的Java代码实现如下:
publicstaticintbackTrackingCoin(int[]coins,intk){//回溯法+动态规划
if(coins==null||coins.length==0||k<1){
return0;
}
int[][]matrix=newint[k+1][coins.length+1];
for(inti=1;i<=k;i++){
for(intj=0;j-1){//只有在不小于0时,preK才能存在于数组matrix中,才能够进行回溯.
matrix[i][j]=matrix[preK][coins.length]+1;//面值i在进行回溯
if(matrix[i][coins.length]==0||matrix[i][j]
代码经过测试,题目给出的测试用例全部通过!
总结
以上就是本文关于Java动态规划之硬币找零问题实现代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题。如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！