暴力递归-记忆化搜索-动态规划（举例）

用户8785253

发布于 2021-07-06 03:52:27

31200

代码可运行

文章被收录于专栏：JAVA学习历程JAVA学习历程

运行总次数：0

代码可运行

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言

任何一个动态规划都是某一种暴力递归的优化求解，故先从暴力递归开始做，改成记忆化搜索（傻缓存），再到动态规划

提示：以下是本篇文章正文内容，下面案例可供参考

一、例子

给一个数组，例如arr[]={2,3,5,10},2,3,5,10是钱数，给一个aim值，钱数可以任意张，问组成aim值的方法数

二、代码

1.暴力递归

代码如下（示例）：

 public static int ways(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim <= 0) {
            return 0;
        }
        return process(arr, 0, aim);

    }

    //暴力递归
    //在arr[index...]之后的钱中任意钱数拿任意张组成rest的方法数
    public static int process(int[] arr, int index, int rest) {
        //base case
        if (rest < 0) {
            return 0;
        }
        //rest>=0
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        //有rest且有钱币可拿的情况
        int ways = 0;
        for (int zhang = 0; (rest - arr[index] * zhang) >= 0; zhang++) {
            ways += process(arr, index + 1, rest - arr[index] * zhang);
        }
        return ways;
    }

2.记忆化搜索（加缓存）

代码如下（示例）：

public static int ways1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim <= 0) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        //一开始所有的过程，都没有计算，缓存为-1
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process1(arr, 0, aim, dp);

    }

    public static int process1(int[] arr, int index, int rest, int[][] dp) {
        //如果缓存中有值，直接返回
        if (dp[index][rest] != -1) {
            return dp[index][rest];
        }
        //缓存中没值，先加缓存再返回,即在return的时候先加缓存，再返回缓存
        //base case
        if (rest < 0) {
            dp[index][rest] = 0;
            return dp[index][rest];
        }
        //rest>=0
        if (index == arr.length) {
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
        //有rest且有钱币可拿的情况
        int ways = 0;
        for (int zhang = 0; (rest - arr[index] * zhang) >= 0; zhang++) {
            ways += process(arr, index + 1, rest - arr[index] * zhang);
        }
        dp[index][rest] = ways;
        return dp[index][rest];
    }

时间复杂度为dp的面积数

3.动态规划（精细化搜索方式）

代码如下（示例）：

public static int ways2(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];
        dp[N][0] = 1;//dp[N][1...aim]第N行其余是0
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <=aim; rest++) {
                int ways = 0;
                for (int zhang = 0; (rest - arr[index] * zhang) >= 0; zhang++) {
                    ways += dp[index + 1][rest - arr[index] * zhang];
                }
                dp[index][rest] = ways;
                return dp[index][rest];
            }
        }
        return dp[0][aim];
    }