算法33：返回组成aim的最少货币张数 —– 从左往右尝试模型

之前对从左到右尝试模型的累加和进行过总结了，概括为：

1. 针对固定集合，值不同，就是讨论要和不要的累加和。算法30有完整的例子

2. 针对非固定集合，面值固定，张数无限。口诀就是讨论要与不要，要的话逐步讨论要几张的累加和。算法31有完整的例子

3. 针对非固定集合，面值固定，张数随机。也就是说有可能只有0张，1张，2张，甚至也是无限的情况。口诀就是在口诀2的基础之上要去除多余项。算法32有完整的例子
 
那么接下来还是从左往右的尝试模型练习，但是这一次并不是要求累加和的问题了，而是要求最小值。

题目：

arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。 每个值都认为是一种面值，且认为张数是无限的。 返回组成aim的最少货币张数。

分析：

1. arr是面值数组，面值固定且没有重复，张数无限。那不就是直接套用口诀2嘛。口诀2是累加和，那我们换成最少张数不就行了。

2. 讨论要与不要，要的话要几张。然后对组合成aim值的张数求最小值。

推导：

1. 假设数组为 {1,2}， aim值为4.

2. 不要1，要2.  要1张aim值只能为2。要2张aim值为4.

3. 不要1，不要2. aim只能为0. 否则没有办法组合成aim为4。

4. 要1，不要2.  要1张，aim只能为1；要2张，aim只能为2，依次类推。只有4张1才能组成4.

5. 要1，要2.   要1张1,1张2. aim只能为3；2张1,1张2，aim可以为4.

步骤2为2张；步骤4为4张；步骤5为3张。最少张数肯定取步骤2的张组合成aim为4.即取2张

递归代码：

 public static int way(int arr[], int aim)
    {
        //-1代表无效
        if (aim < 0 || arr == null || arr.length == 0) {
            return -1;
        }

        int ans = process(arr, 0, aim);
        return Integer.MAX_VALUE == ans ? -1 : ans;
    }

    public static int process (int[] arr, int index, int aim)
    {
        //数组越界
        if (index == arr.length) {
            //如果目标值为0, 则需要0张货币; 否则，无法凑到aim值，返回无效值
            return aim == 0 ? 0 : Integer.MAX_VALUE;
        }

        int count = Integer.MAX_VALUE;
        for (int zhangshu = 0; zhangshu * arr[index] <= aim; zhangshu++) {
             //返回张数
             int ans = process(arr, index + 1, aim - zhangshu * arr[index]);

             //如果返回值有效
            if (ans != Integer.MAX_VALUE) {
                count = Math.min(count, zhangshu + ans);
            }
        }

        return count;
    }

动态规划:

动态规划是可以根据递归直接得到的。技巧就是递归的base case就是动态规划初始行的值。递归的逻辑直接照搬到动态规划的代码中来。

而本例子中递归的base case为 ：

if (index == arr.length) {
    //如果目标值为0, 则需要0张货币; 否则，无法凑到aim值，返回无效值
    return aim == 0 ? 0 : Integer.MAX_VALUE;
}

1.首先构建二维表

2. 根据递归的base case ：

if (index == arr.length) {
    //如果目标值为0, 则需要0张货币; 否则，无法凑到aim值，返回无效值
    return aim == 0 ? 0 : Integer.MAX_VALUE;
} 

可得到：

3. 根据递归的逻辑：

int count = Integer.MAX_VALUE;
for (int zhangshu = 0; zhangshu * arr[index] <= aim; zhangshu++) {
     //返回张数
     int ans = process(arr, index + 1, aim - zhangshu * arr[index]);

     //如果返回值有效
    if (ans != Integer.MAX_VALUE) {
        count = Math.min(count, zhangshu + ans);
    }
}

推导row下标为1的行：

4. 推导row下标为0的行

那么，最终的推导结果为：

因此，动态规划代码可以这么改：

 //动态规划
    public static int dp1(int[] arr, int aim) {
        //-1代表无效
        if (aim < 0 || arr == null || arr.length == 0) {
            return -1;
        }

        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];

        //根据递归base case ： index == arr.length可得，dp最后一行的初始值
        dp[N][0] = 0;
        for (int i = 1; i <= aim; i++) {
            //无效值
            dp[N][i] = Integer.MAX_VALUE;
        }

        //动态规划老套路，双层for循环。以arr数组为行，以aim为列
        //最后一行已经初始化，需要从倒数第二行开始推导
        for (int row = N - 1; row >= 0; row--) {
            for (int col = 0; col <= aim; col++) {
                //从左往右尝试模型，开始讨论要与不要。要的话，到底要几张
                //完全照抄递归的逻辑
                int count = Integer.MAX_VALUE;
                for (int zhangshu = 0; zhangshu * arr[row] <= col; zhangshu++) {
                    //返回张数。递归中此处是递归的调用。此处直接换成依赖关系
                    int ans = dp[row + 1][col - (zhangshu * arr[row])];
                    //如果返回值有效
                    if (Integer.MAX_VALUE != ans) {
                        count = Math.min(count, zhangshu + ans);
                    }
                }
                dp[row][col] = count;
            }
        }

        return dp[0][aim] == Integer.MAX_VALUE ? -1 : dp[0][aim];
    }

我们以肉眼可见的速度发现，动态规划的时间复杂度为 O(arr.length * aim * aim).  而之前我们已经分析过此类动态规划是可以对时间复杂度进行优化的。下面进行优化过程的逐步推导:

假设aim为6 ，结果该如何呢？

value为1的情况，肯定是6张

value为2的情况，肯定是3张

value为1和2的组合，最少张数是多少呢？数数手指头肯定是2张2和2张1的组合呀，即4张。

推导：

第一步

第二步：

第三步：

既然有这样的归类，那么我们之前的0、1、2、3、4是不是也具有这样的规则呢？尝试一下看看

首先尝试row=1的行

接下来，我们再来尝试row=0的行：

我们发现，按照这样的推导过程，结果全部正确。既然正确，说明这个公式是大概率成立的。那么，我们尝试对动态代码的时间复杂度进行优化：

动态规划 + 时间复杂度：

//动态规划 + 时间复杂度优化
    public static int dp2(int[] arr, int aim) {
        //-1代表无效
        if (aim < 0 || arr == null || arr.length == 0) {
            return -1;
        }

        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];

        //根据递归index == arr.length可得，dp最后一行的初始值
        dp[N][0] = 0;
        for (int i = 1; i <= aim; i++) {
            //无效值
            dp[N][i] = Integer.MAX_VALUE;
        }

        //动态规划老套路，双层for循环。以arr数组为行，以aim为列
        //最后一行已经初始化，需要从倒数第二行开始推导
        for (int row = N - 1; row >= 0; row--) {
            for (int col = 0; col <= aim; col++) {
                //下一行当前列
                dp[row][col] =  dp[row + 1][col];
                
                //col - arr[row] ： 前一个value对应的下标有效
                if (col - arr[row] >= 0
                        && dp[row][col - arr[row]] != Integer.MAX_VALUE) {
                    /**
                     * 此处，为什么 dp[row][col - arr[row]] + 1 ？
                     * 
                     * dp[row][col - arr[row]]为当前行前一个aim对应的下标。 那么当前列的aim
                     * 肯定是 dp[row][col - arr[row]]对应的aim 加上 1 * value。
                     * 
                     * 即 dp[row][col]对应的aim = dp[row][col - value]对应的aim + 1 * value
                     * 说的简单点，就是当前行多加1个value值而已。
                     * 
                     * 既然value值需要多加上1张，那么张数肯定是也是要多加1的。
                     * 
                     * 前一个value列 和 下一行当前列，肯定是取小
                     * 
                     */
                    dp[row][col] = Math.min(dp[row][col], dp[row][col - arr[row]] + 1);
                }
            }
        }

        return dp[0][aim] == Integer.MAX_VALUE ? -1 : dp[0][aim];
    }

这一切都只是我们的推理而已，那么接下来就是海量数据的测试了。加上对数器进行测试：

完整代码

package code03.动态规划_07.lesson4;

/**
 * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * 每个值都认为是一种面值，且认为张数是无限的。
 *
 * 返回组成aim的最少货币张数
 */
public class MinPaperNoLimit_07 {

    public static int way(int arr[], int aim)
    {
        //-1代表无效
        if (aim < 0 || arr == null || arr.length == 0) {
            return -1;
        }

        int ans = process(arr, 0, aim);
        return Integer.MAX_VALUE == ans ? -1 : ans;
    }

    public static int process (int[] arr, int index, int aim)
    {
        //数组越界
        if (index == arr.length) {
            //如果目标值为0, 则需要0张货币; 否则，无法凑到aim值，返回无效值
            return aim == 0 ? 0 : Integer.MAX_VALUE;
        }

        int count = Integer.MAX_VALUE;
        for (int zhangshu = 0; zhangshu * arr[index] <= aim; zhangshu++) {
             //返回张数
             int ans = process(arr, index + 1, aim - zhangshu * arr[index]);

             //如果返回值有效
            if (ans != Integer.MAX_VALUE) {
                count = Math.min(count, zhangshu + ans);
            }
        }

        return count;
    }


    //动态规划
    public static int dp1(int[] arr, int aim) {
        //-1代表无效
        if (aim < 0 || arr == null || arr.length == 0) {
            return -1;
        }

        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];

        //根据递归base case ： index == arr.length可得，dp最后一行的初始值
        dp[N][0] = 0;
        for (int i = 1; i <= aim; i++) {
            //无效值
            dp[N][i] = Integer.MAX_VALUE;
        }

        //动态规划老套路，双层for循环。以arr数组为行，以aim为列
        //最后一行已经初始化，需要从倒数第二行开始推导
        for (int row = N - 1; row >= 0; row--) {
            for (int col = 0; col <= aim; col++) {
                //从左往右尝试模型，开始讨论要与不要。要的话，到底要几张
                //完全照抄递归的逻辑
                int count = Integer.MAX_VALUE;
                for (int zhangshu = 0; zhangshu * arr[row] <= col; zhangshu++) {
                    //返回张数。递归中此处是递归的调用。此处直接换成依赖关系
                    int ans = dp[row + 1][col - (zhangshu * arr[row])];
                    //如果返回值有效
                    if (Integer.MAX_VALUE != ans) {
                        count = Math.min(count, zhangshu + ans);
                    }
                }
                dp[row][col] = count;
            }
        }

        return dp[0][aim] == Integer.MAX_VALUE ? -1 : dp[0][aim];
    }


    //动态规划 + 时间复杂度优化
    public static int dp2(int[] arr, int aim) {
        //-1代表无效
        if (aim < 0 || arr == null || arr.length == 0) {
            return -1;
        }

        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];

        //根据递归index == arr.length可得，dp最后一行的初始值
        dp[N][0] = 0;
        for (int i = 1; i <= aim; i++) {
            //无效值
            dp[N][i] = Integer.MAX_VALUE;
        }

        //动态规划老套路，双层for循环。以arr数组为行，以aim为列
        //最后一行已经初始化，需要从倒数第二行开始推导
        for (int row = N - 1; row >= 0; row--) {
            for (int col = 0; col <= aim; col++) {
                //下一行当前列
                dp[row][col] =  dp[row + 1][col];

                //col - arr[row] ： 前一个value对应的下标有效
                if (col - arr[row] >= 0
                        && dp[row][col - arr[row]] != Integer.MAX_VALUE) {
                    /**
                     * 此处，为什么 dp[row][col - arr[row]] + 1 ？
                     *
                     * dp[row][col - arr[row]]为当前行前一个aim对应的下标。 那么当前列的aim
                     * 肯定是 dp[row][col - arr[row]]对应的aim 加上 1 * value。
                     *
                     * 即 dp[row][col]对应的aim = dp[row][col - value]对应的aim + 1 * value
                     * 说的简单点，就是当前行多加1个value值而已。
                     *
                     * 既然value值需要多加上1张，那么张数肯定是也是要多加1的。
                     *
                     * 前一个value列 和 下一行当前列，肯定是取小
                     *
                     */
                    dp[row][col] = Math.min(dp[row][col], dp[row][col - arr[row]] + 1);
                }
            }
        }

        return dp[0][aim] == Integer.MAX_VALUE ? -1 : dp[0][aim];
    }




    // 为了测试
    public static int[] randomArray(int maxLen, int maxValue) {
        int N = (int) (Math.random() * maxLen);
        int[] arr = new int[N];
        boolean[] has = new boolean[maxValue + 1];
        for (int i = 0; i < N; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue) + 1;
            } while (has[arr[i]]);
            has[arr[i]] = true;
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
     /*  int[] arr = {1,5, 14, 2};
        int aim = 16;

        System.out.println(way(arr, aim));
        System.out.println(dp1(arr, aim));
        System.out.println(dp2(arr, aim));*/

        int maxLen = 10;
        int maxValue = 20;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int aim = (int) (Math.random() * maxValue);
            int ans1 = way(arr, aim);
            int ans2 = dp1(arr, aim);
            int ans3 = dp2(arr, aim);

            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println("Oops!");
                printArray(arr);
                System.out.println(aim);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println(ans3);

                break;
            }
        }
        System.out.println("测试结束");
    }
}

代码007普通

打赏 收藏 海报 链接