[动态规划]凑零钱.钱币的组合有多少种(java)网站首页 技术教程

[动态规划]凑零钱.钱币的组合有多少种(java)

SP_1024 2024-09-08 00:01:03

简介[动态规划]凑零钱.钱币的组合有多少种(java)

钱币的组合有多少种

arr是面值数组，其中的值都是正数且没有重复。
再给定一个正数aim。
每个值都认为是一种面值，且认为张数是无限的。
返回组成aim的方法数
例如：arr = {1,2}，aim = 4
方法如下：1+1+1+1、1+1+2、2+2 一共就3种方法，
所以返回3

暴力递归

解题思路

每种钱币都有无数张,在钱币的数组中,我们每来到一种钱币时,我们都要考察其选择0张一张两张…一直到面额相加超出aim 为止.因此递归遍历时,我们要遍历选择的张数.
base case 就很好定了,选择范围超出钱币数组时,和aim 小于0时.
开撸代码

代码演示

  /**
     * 计算有多少种组合
     * @param arr 钱币数组
     * @param aim 要组成的钱币
     * @return
     */
    public static int coinsWay(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process(arr,0,aim);
    }

    /**
     * 暴力递归
     * @param arr 钱币数组
     * @param index 钱币数组下标,代表选择到哪个钱币了
     * @param aim 要组成的钱币
     * @return
     */
    public static int process(int[]arr,int index ,int aim){
        //base case 小于0 钱币组合无效 返回0
        if (aim < 0){
            return 0;
        }
        //来到最后,没有能选择的钱币了,此时 aim == 0 代表前面选择有效 返回1 否则返回0
        if(index == arr.length){
            return aim == 0 ? 1 : 0;
        }
        int ans = 0;
        //循环确定每种钱币选择的张数,不能超过aim
        for (int i = 0; arr[index] * i <= aim; i++){
            ans += process(arr,index + 1,aim - (arr[index] * i));
        }
        return ans;
    }

动态规划

解题思路:

动态规划就是改写暴力递归,递归的过程就是状态转移方程
总共分三步:
1,根据base case 初始化动态规划表
2.根据递归过程,写出状态转移方程
3.返回递归调用的原始状态.

代码演示

    /**
     * 动态规划
     * @param arr
     * @param aim
     * @return
     */
    public static int dp(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        //动态规划表
        int[][] dp = new int[N + 1][aim + 1];
        //根据base case  初始化表
        dp[N][0] = 1;
        //根据递归过程写出状态转移方程
        for (int i = N - 1;i >= 0;i--){
            for (int j = 0;j <= aim;j++){
                int ans = 0;
                for (int k = 0; arr[i] * k <= j; k++){
                    ans += dp[i + 1][j - (arr[i] * k)];
                }
                dp[i][j] = ans;
            }
        }
        //返回调用递归的初始状态
        return dp[0][aim];
    }