[程序员代码面试指南]递归和动态规划-换钱的方法数（DP，完全背包）

佚名 6年前 (2019-05-10) 随笔 1422人围观抢沙发百度已收录

题目描述

给定arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim，求组成aim的方法数。

解题思路

完全背包
和“求换钱的最少张数”的转移来的状态完全相同。
初始化不同
转移方程为：dp[i][j]=dp[i-1][j]+dp[i][j-arr[i]]

代码

public class Solution {
    public int getMeansCnt(int arr[],int aim){
        int[] dp=new int[aim+1];
        
        //initial 
        for(int j=0;j<=aim;++j) {
            dp[j]=0;
        }
        for(int k=0;arr[0]*k<=aim;++k) {//
                dp[arr[0]*k]=1;
        }
        
        for(int i=1;i<arr.length;++i) {
            for(int j=arr[i];j<=aim;++j) {
                dp[j]=dp[j]+dp[j-arr[i]];//
            }
        }
        
        return dp[aim];
    }
}