【手撕代码】背包问题：数组中任意数累加得到目标值（递归+动态规划）

旧城等待， 2022-02-15 02:13 140阅读 0赞

> 问题：给你一个数组 arr，和一个整数 aim。如果可以任意选择 arr 中的数字，能不能累加得到 aim，返回 true 或者 false。

### 一、递归版本 ###

【分析】：每个位置 i 有 要和不要 两种选择；叶节点会看自己这里的结果是不是 aim，从而向父结点返回 true 或 false，父结点比较子节点的结果，有一个为 true 就一直返回 true，否则返回 false。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

>  *  分析：
> 
> 如上图所示：数组 arr = \{3, 2, 5\} ，aim = 7：
> 
> f(0, 0)：代表0位置处状态值为 0 的点；
> 
> f(2, 5)：代表2位置处状态值为 5 的点。
> 
> 只要有叶节点的值等于 aim 的值，则会返回 true。

*  **递归版本代码实现**

public class SumToAimWithRecursion {
    
        public static boolean isSumToAim(int[] arr, int aim){
            if(arr == null || arr.length < 1){
                return false;
            }
            return process(arr, 0, 0, aim);
        }
    
        /**
         * @param arr：数组
         * @param i：数组下标为 i 的位置
         * @param sum :数组前 i - 1 个数决策累加的结果
         * @param aim : 目标值
         * @return：是否存在累加值等于目标值
         */
        public static boolean process(int[] arr, int i, int sum, int aim){
            // 递归终止条件
            if(i == arr.length){
                // 说明数组中所有的数都已经决策累加过了
                return sum == aim;
            }
    
            // 数组中下标为 i 的数可以要也可以不要，有两种选择
            // 最后有一个等于aim，一路往上都返回true
            return process(arr, i + 1, sum, aim) || process(arr, i + 1, sum + arr[i], aim);
        }
    }

--------------------

### 二、动态规划版本 ###

>  *  分析：
> 
> 判断是否为无后效性：是无后效性的；
> 
> 确定可变参数：i 值，sum 值，aim 值是固定的；
> 
> 确定二维状态表（两个可变参数）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

状态表如上图所示，横坐标为 m 的值，纵坐标为 i 的值。从 baseCase 可以看出最后一行的状态值是可以确定的，所以从最后一行往上推导，一直推导到左上角的位置处，如果为 True，则返回 True（图中空白处都为false）。

怎么通过下面一行的状态值得出上面一行的状态值呢？看递归的代码：

process(arr, i + 1, sum, aim) || process(arr, i + 1, sum+ arr[i], aim)

因此：**dp\[i\]\[sum\] 为 true 有两种情况：dp\[i + 1\]\[sum\] 为 true 或者 dp\[i+1\]\[sum+arr\[i\]\]为 ture**，两个有一个为 true 就可以了。

*  **动态规划代码实现**

public class SumToAimWithDynamic {
    
        public static boolean isSumToAim(int[] arr, int aim){
            if(arr == null || arr.length < 1){
                return false;
            }
    
            // 构建状态表：要注意在原数组长度基础上加1
            // 可变参数：i 和 sum  只需要关心 aim 之前的累加和就好了
            boolean[][] dp = new boolean[arr.length + 1][aim + 1];
    
            // baseCase：填好dp的最后一行，上面每一行的dp值都依赖下面一行的dp值得出
            for(int i = arr.length, sum = 0; sum <= aim; sum++){
                if(sum == aim){
                    dp[i][sum] = true;    // 目标值处设置为 true
                }else{
                    dp[i][sum] = false;
                }
            }
    
            // 其他位置的 dp 值：依赖下一行位置的两个位置处的 dp 值
            for(int i = arr.length - 1; i >= 0; i--){
                for(int sum = aim; sum >= 0; sum--){
                    if(sum + arr[i] > aim){
                        // 填充最后一列的 dp 值,其实一个为 true，正上方的位置都为 true
                        dp[i][sum] = dp[i + 1][sum];
                    }else{
                        // dp[i][sum]为true有两种情况：dp[i+1][sum]为true或者dp[i+1][sum+arr[i]]为ture
                        dp[i][sum] = dp[i + 1][sum] || dp[i + 1][sum + arr[i]];
                    }
                }
            }
            return dp[0][0];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220215/2952f01893d6480dbbaab6539e590194.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220215/a05d06318c844a94bc8baef06e9bdea9.png