完整博文地址

• 由于CSDN的图片导入机制的问题，导致在本地编写的md文档中的图片无法上传到CSDN上，因此我把博文push到了gitee上，以下是地址:请点击:我的博文地址

2.14 经典动态规划:戳气球问题

2.14.1 题意解析

• 输入一个包含非负整数的数组nums代表一排气球,nums[i]代表第i个气球的分数，现在要求戳破所有气球，请计算最多可能获得的分数
• 得分的计算规则如下:当戳破第i个气球的时候，可以获得nums[left]*nums[i]*nums[right]
• 备注:当i走到边界的时候,也就是left=-1,或者right=n的时候，这时候它们的值被设置为1
• 同时需要注意的是left和right不一定是i-1和i+1这两个值，而是根据戳破气球的序列来确定的
• 直接暴力模拟的想法:一共n个位置,我们算出n个位置的全排列序列下的得分，取最大值，一定可以得到答案
• 一看，这就是大量穷举，为了通过这道题，我们需要进行剪枝，这恰恰就是动态规划的特征

2.14.2 回溯思路

• 只要是设计到求最值，一定是穷举所有可能的结果，然后对比得出最值
• 穷举主要有两种算法，分别是回溯算法和动态规划，前者就是暴力穷举，而后者是根据状态转移方程推导"状态"
• 我们可以先通过回溯思想来编写出基本的解法
• 回溯的要点主要是:做出选择后推进+撤销选择

    private int res = Integer.MIN_VALUE;
    public int maxCoins(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }//对数值赋值一份
        backTrack(list,0);
        return res;
    }


    private void backTrack(ArrayList<Integer> list, int score){
        if(list.isEmpty()){
            res = Math.max(res,score);
            return;
        }
        for(int i = 0;i<list.size();i++){
            int temp = list.get(i);//记忆起来,防止忘记
            int tempCoin = list.get(i)*( i-1<0 ? 1: list.get(i-1)) * (i+1 >= list.size() ?1 : list.get(i+1));
            //做选择
            list.remove(i);//选择了第i个,然后就把第i个给删除掉
            backTrack(list,score + tempCoin);
            //撤销选择
            list.add(i,temp);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 分析一下算法的效率,第一个位置有n个选择，第二个位置有n-1个选择，…，因此总的时间复杂度是O(n!),题目给的n的规模是500，直接超时的

2.14.3 动态规划思路

• 在之前说过使用动态规划算法的一个重要条件是子问题必须独立，而在这道题中，每戳破一个气球nums[i]，得到的分数和该气球相邻的气球nums[left]和nums[right]是有相关性的，而这种情况下就是子问题间产生了相互联系，不独立，彼此间有着耦合关系，因此我们必须巧妙地定义dp数组的含义，避免子问题产生相关性，才能写出状态转移方程
• 考虑这样一个想法:题目中给出条件，戳第零个气球和戳第n-1个气球,其超出边界的那一个气球就算作1分,那么我们是否可以这样想，题目中设定了两个虚拟气球，这两个虚拟气球戳中就给1分，然后我题目的要求就转换为了按照一定顺序戳[1,n]的气球，而戳[1,n]的气球，是不是可以转换成分开戳各个离散的区间内的气球，然后找到一种最佳的组合，使得最终气球序列只剩下0和n+1号气球，最多能够得到多少分?，一旦作出了这样的问题转换，我们就可以思考一下,戳**[i,j-1]和[j,n]**这两个区间内的气球，这两个区间的得分情况是否是独立的呢?
• 很显然是独立的，这样我们就完成了dp[i][j]数组的定义，三步走
• dp[i][j]:代表着戳(i,j)区间所能得到的最大得分,注意这是开区间哈，不包含i和j两个断点，同时容易得到最终答案应该是dp[0][n+1]
• base-case:当0<=i<=n+1,j<=i+1的时候,dp[i][j] = 0
• 状态转移方程推导
  • 如果是正向思考，我们不难得到，我们可以依次枚举每个区间内的全排列（回溯），以此来计算出每个区间内的最大得分，这也就是2.14.2里面写的那一种，但是我们通过分析其时间复杂度，是绝对过不了这道题的
  • 因此，正难则反，我们正向思考是从戳第一个气球到戳最后一个气球，那么反就是我们从最后一个气球回溯到最初始的状态，我们在处理(i,j)区间里边的时候，想一想哪个气球会是最后被戳破的那一个
  • 实际上这区间里边的所有气球都有可能是最后一个被戳破的气球，那么我们不妨假定这个被戳破的气球是k，那么这个k如何确定呢，也就是选择来的
  • 经过上述分析，我们明确了，状态就是i和j的值移动情况,选择就是选择哪个气球为k
  • 由于最后是戳破气球k,那么我们回溯到上一步发生了啥,也就是我们至少得先要把(i,k)、(k,j)里面的气球都给戳破，所以我们可以通过dp数组来算这个值先，然后戳破第k个气球的时候,会得分,由于k已经是最后一个气球了，又根据dp数组的定义，这时候它左右两边的气球是i和j，所以可以根据这个来计算得分
  • 那么如何来求极值呢?依然是穷举，但是此时的穷举，是穷举k，穷举在(i,j)之内的所有k,看谁能够得到本区间的最大值

dp[i][j] = dp[i][k] + dp[k][j] + (points[i]*point[k]*point[j])
1

• 三步走完成后，我们会发现base-case给的是对角线上的值，因此顺序遍历是行不通的，我们来观察DP-Table，我们确定遍历顺序的关键是状态转移所依赖的状态必须被提前计算出来，思路也是有的，也就是根据base-case和最终状态进行推导

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5056N6gC-1659781449019)(./image/312-1.png)]

• 我们发现base-case分布在对角线上,而最终答案确定是在DP-Table的右上角，对于任意一个dp[i][j],我们希望所有dp[i][k]和dp[k][j]已经被计算

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HpHmy3mV-1659781449020)(./image/312-2.png)]

• 提出两种可行的遍历方案

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FY8ufYjv-1659781449021)(./image/312-3.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kVFle9eM-1659781449022)(./image/312-4.png)]

• 斜着遍历的方式是比较困难的，我们选择第二种的方式来进行遍历，这种遍历的方式能够确保在遍历的时候，其左边和下边的元素都已经被计算出来了，可以手工验算一下

class Solution {
    public int maxCoins(int[] nums) {
        //1.扩展数组
        int n = nums.length;
        int[] points = new int[n+2];
        points[0]=points[n+1]=1;
        for(int i = 1;i<points.length-1;i++){
            points[i] = nums[i-1];
        }
        //2.定义dp数组,注意(i,j)是开区间,代表这个区间内的所能得到的最大得分,最小下标0,最大下标n+1
        int[][] dp = new int[n+2][n+2];
        //3.写出base-case,注意到dp的区间是(i,j),所以当j<=i+1的时候就压根就没有这个区间,那么也就压根没有最大值可以选了
        //想一下(i,i+1)这个区间有值吗?至少得相差个2吧
        for(int i =0;i<=n+1; i++){
            for(int j = 0;i!=n+1&&j<=i+1;j++){
                dp[i][j] = 0;
            }
        }
        //4.状态转移推算,从下到上,从中间对角线到右上角,保证每一个值的下边和左边都被计算过了,因为n+1的那一行已经被计算过了(base-case),因此直接从n开始算
        for(int i = n;i>=0;i--){
            for(int j = i+1 ; j<n+2; j++){
                //做选择,从(i,j)里面选一个k出来
                for(int k = i+1;k<j;k++){
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i][k]+dp[k][j]+(points[k]*points[i]*points[j]));
                }
            }
        }
        return dp[0][n+1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.15 经典动态规划问题:0-1背包问题

2.15.1 题意解析

• 给一个可装重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，选择让你用这个背包来装物品，最多能装的价值是多少?
• 同样的，这道题也可以通过穷举来解，也就是计算出一组数(全排列)穷举来得到最大值，暴力穷举无法通过此题，那么要剪枝，这就是动态规划思路的特征
• 同时由于题意比较明显，状态和选择比较明显

2.15.2 动态规划标准套路

• 直接开始三步走

• 明确状态和选择

  • 只要给定几个物品和一个背包的容量限制，就形成了一个背包问题
  • 所以状态有两个，就是背包的容量和可选择的物品
  • 选择就是对于每件物品而言，装进背包或者不装进背包

• 明确dp数组的含义

  • 根据状态和选择来定义dp数组即可
  • dp[i][w]:对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]

• base-case

  • base-case就是当没有物品可以选或者当前背包的容量为0的时候，能装的价值就是0了

• 确定状态转移方程:状态转移与选择息息相关

  • 如果没有把这第i个物品装入背包，那么dp[i][w]应该要等于dp[i-1][w]，因为不选这个物品，那么背包容量就还是w，继承之前的结果
  • 如果把这第i个物品装入背包，那么dp[i][w]=dp[i-1][w-wt[i-1]]+val[i-1]:如果装了第i个物品，就要寻求剩余重量w-wt[i-1]限制下的最大价值，再加上第i个物品的价值val[i-1]即可
  • 注:由于i是从1开始的所以val和wt的索引是i-1时表示第i个物品的价值和重量

    public int backPack(int W,int N,int[] wt,int[] val){
        //1.定义dp数组,dp[i][w]是指对于前i个物品,当前背包容量为w,这时候所能得到的最大价值
        //要确定数组的大小,必须确定最终的答案:dp[N][W]
        int[][] dp = new int[N+1][W+1];
        //2.写出base-case,当i或者w有其中有一个等于0的时候,这个值就是0
        dp[0][0] = 0 ;
        for(int i = 1;i <= N;i++){
            dp[i][0] = 0;
        }
        for(int w = 1;w <= W ; w++){
            dp[0][w] = 0;
        }
        //3.写出状态转移方程
        //3.1 确定遍历顺序:根据DP-table,容易知道,此时Dp-table被初始化为第0列为0,第0行为0的一个正方形表
        //3.1 根据状态转移方程,容易知道,我们希望得到的是这个元素的左上角已经被全部计算完了,因此遍历顺序是顺序遍历的(可以画图验证)
        for(int i = 1; i <= N;i++){
            for(int j = 1; j <= W;j++){
                //现在试图装第i-1个物品
                if(j-wt[i-1]<0){//如果现在装不下,那么只能选择不装进背包
                    dp[i][j] = dp[i-1][j];
                }else{//否则就是可以装下背包,有选择的余地
                    dp[i][j] = Math.max(
                            dp[i-1][j],//选择不装入背包,继承不装这个东西进背包,但容量保持这么多的
                            dp[i-1][j-wt[j]]+val[i-1]//选择装入背包
                    );
                }
            }
        }
        return dp[N][W];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.16 经典动态规划:子集背包问题

2.16.1 题意分析

• 输入一个只包含正整数的非空数组nums，判断这个数组是否可以被分割成两个子集，使得两个子集的元素和相等
• 对于背包问题而言，给一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性，其中第i个物品的重量为wt[i]，价值为val[i]，现在用这个物品装物品，最多能装的价值是多少?
• 那么这个问题，可以先对集合求和，求出sum，将问题转化为背包问题:
• 给一个可装载重量为sum/2的背包和N个物品，每个物品的重量为nums[i]，现在让你装物品，是否存在一种装法能够恰好将背包给装满?

2.16.2 思路分析

• 明确dp数组的含义:dp[i][j]=x表示，对于前i个物品，当前背包的容量为j时，若x为true，则说明可以恰好将背包给装满，若x为false，则说明不能恰好将背包给装满,比如说dp[4][9]=true:对于容量为9的背包，若只使用前4个物品，则存在一种方法恰好将背包装满
• 通过上述的分析可知，我们相求的最终答案就是dp[N][sum/2],base-case就是当背包没有空间的时候，你都已经可以不用选了，因为这时候已经装满了，那么就是true，当没有物品可以选择的时候，如果这时候背包容量还不是空，那么就肯定装不满了
• 分析状态转移
• 如果不把nums[i]算入子集，那么取决于上一个状态dp[i-1][j]，继承之前的结果
• 如果把nums[i]算入子集，那么是否能够恰好装满背包，取决于状态dp[i-1][j-nums[i-1]]，如果装了第i个物品，就要看背包的剩余重量j-nums[i-1]限制下是否能够恰好装满，换句话说错，如果j-nums[i-1]的重量可以被恰好装满，那么只要把第i个物品装进去，也可以恰好装满j的重量，否则肯定是不能够恰好装满重量j的

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%2!=0){return false;}
        int n = nums.length;
        sum /=2;
        boolean[][] dp = new boolean[n+1][sum+1];
        for(int i =0;i<=n;i++){
            dp[i][0] = true;
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=sum;j++){
                if(j-nums[i-1]<0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.16.3 状态压缩优化

• 可以看出,dp[i][j]都是通过上一行dp[i-1][...]转移过来的，所以可以压缩成一维的

    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%2!=0){
            return false;
        }
        sum/=2;
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;
        for(int i = 0;i<n;i++){
            for(int j = sum;j>=0;j--){
                if(j-nums[i]>=0){
                    dp[j] = dp[j] || dp[j-nums[i]];
                }
            }
        }
        return dp[sum];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.17 完全背包问题

2.17.1 题意解析

• 给定不同面额的硬币coins和一个总金额amount，写一个函数来计算可以凑成总金额的硬币组合数，假设每一种面额的硬币有无限个

• 翻译成背包问题的说法:有一个背包，其最大容量是amount，有一系列的物品coins，每个物品的重量是coins[i],每个物品的数量无限，请问存在多少种方法能够把背包恰好给装满?

2.17.2 解题思路

• 首先是动态规划三步走

• 第一明确两点，“状态"和"选择”

  • 状态有两个，就是背包的容量和可选的物品
  • 选择就是选择装进背包或者不装进背包

• 确定dp数组的含义:dp[i][j]可以用来表示若只使用前i个物品，当背包容量为j的时候，有dp[i][j]种方法可以装满背包，若只使用coins的前i个物品，当背包容量为j的时候，有dp[i][j]种凑法

• 写出base-case:当i=0的时候，也就是没有东西可以选了，这时候有0种凑法，当j=0的时候，表示当前背包容量为0,这时候有0种凑法

• 最终得到算法的输出是dp[N][amount]

• 确定状态转移方程

  • 如果不把这第i个物品装入背包，也就是说不使用coins[i]这个面值的硬币，那么凑出面额j的方法数dp[i][j]应该要等于dp[i-1][j]，继承之前的结果
  • 如果把这个第i个物品装入背包，那么dp[i][j]应该要等于dp[i][j-coins[i-1]]
  • 注:由于i是从1开始的，所以coins的索引是i-1时表示第i个硬币的面值
  • 理解:比如说想用面值为2的硬币凑出金额5，如果知道了凑出金额3的方法，在加上一枚面额为2的硬币，就可以凑出5了
  • 对于最终的答案，我们希望知道总共有多少种凑法，所以dp[i][j]是选择和不选择两种选择所产生的凑法之和

    public int change(int amount, int[] coins) {
        //1.定义dp数组,dp[i][j]:表示的是选择前i个物品,在j的背包容量下,共有几种凑法
        int[][] dp = new int[coins.length+1][amount+1];
        //2.定义base-case
        //当i=0的时候,表示没有硬币可以选
        //当j=0的时候,表示背包没有容量,如果背包没有容量,那么这也是一种凑法,因为根据定义来说,我们都根本不用选硬币
        dp[0][0]=0;
        for(int i = 0;i<=coins.length;i++){
            dp[i][0] = 1;
        }
        for(int j = 0;j<=amount;j++){
            dp[0][j] = 0;
        }
        //3.开始状态转移计算,由base-case得到的DP-table可知从(1,1)开始
        for(int i = 1;i<=coins.length;i++){
            for(int j = 1;j<= amount; j++){
                //如果当前的背包容量装不下,那么只能够不选
                if(j-coins[i-1] <0 ){
                    dp[i][j] = dp[i-1][j];
                }else{
                    //如果装得下,那么我们把两种凑法都纳入进来
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[coins.length][amount];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2.18 动态规划典型例题–打劫问题

2.18.1 基本题意分析

• 街上有一排房屋，用一个包含非负整数的数组nums表示，每个元素nums[i]代表第i间房子中的现金数额，现在你可以从房子中取钱，但是有一个约束条件，相邻的房子的钱不能被同时取出(或者其他条件)，你需要尽可能多地取出钱，请你编写一个算法，计算在满足调节的前提下最多能够取出多少钱?
• 我们可以对题意进行解析，这道题存在着比较明显的选择和状态
• 选择：是否拿走当前这个屋子的钱?
• 状态：当前走到哪一座房子了
• 如果你取出这间房子的钱，那么对于相邻的下一间房子，肯定不能再取钱了，只能从下下间房子开始做选择
• 如果你不取出这间房子的钱，那么可以走到下一间房子前，继续做选择
• 当你走过了最后一间房子，就没办法做选择了，能获得的现金数目显然是0(base-case)，可以先写出dp函数来理清楚思路

2.18.2 线性排列情况

• 自顶向下的解法

    private int[] memo;
    public int rob(int[] nums) {
        memo = new int[nums.length+5];
        Arrays.fill(memo,-1);
        return dp(nums,0);//从0开始走过
    }

    /**
     * dp函数的定义:表示对于一个数组nums,从start开始走,能够抢劫得到的最大金额是多少?
     * @param nums
     * @param start
     * @return
     */
    private int dp(int[] nums,int start){
        //start代表的是索引,表示目前的状态,当start大于等于nums.length了,这时候不可能在抢劫了,是空区间,返回0值
        if(start >= nums.length){//由于可能存在+2的情况,因此这里写>=
            return 0;
        }
        //备忘录优化
        if(memo[start] != -1){
            return memo[start];
        }
        //择优,取max
        int res = Math.max(
                dp(nums,start+2)+nums[start],//选择抢这个屋子的
                dp(nums,start+1)//选择不抢这个屋子的
        );
        memo[start] = res;
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 自底向上解法

• 我们可以根据dp()的原型，定义出dp数组,dp(int i)定义的是从i开始打劫,能够得到的最大金额是多少

• 那么dp[i]可以定义为，从第i间房子开始做选择,能够得到的最大金额是多少

• 遍历方向要根据base-case所定义的DP-table来决定,我们规定，当从第n间房子开始走的时候，这时候能取到的钱是0,那么也就是最后一个元素是0，那么我们遍历就要从倒数第二个元素来开始遍历

    public int rob(int[] nums) {
        int[] dp = new int[nums.length+2];
        dp[nums.length] = 0;
        for(int i = nums.length-1;i>=0;i--){
            dp[i] = Math.max(
                    dp[i+1],//当累加上一间房子的最大金额,就代表着上一间房子被拿了,那么这里就不加
                    dp[i+2]+nums[i]//当累加上两间房子的最大金额,就代表是上两件房子被拿
            );
        }
        return dp[0];
    }
1
2
3
4
5
6
7
8
9
10
11

• 状态压缩

    public int rob(int[] nums) {
        int dp_i_1 = 0,dp_i_2=0,dp_i=0;
        for(int i= nums.length-1;i>=0;i--){
            dp_i = Math.max(dp_i_1,nums[i]+dp_i_2);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
1
2
3
4
5
6
7
8
9

2.18.3 环形排列情况

• 这道题是上一道的升级版，其主要限制是限制了临界的下标，一旦越过了临界下标，就是环的起点，这种房屋是不能够连环访问的
• 我们将这个条件加入到我们的考虑中，来看看选择发生了什么变化?
• 首尾房间不能同时取钱，那么只可能有三种不同的情况
• 第一间房子和最后一间房子都不取钱
• 只取第一间房子的钱而不取最后一间房子的钱
• 只取最后一间房子的钱，而不取第一间房子的钱
• 同时我们容易知道，由于取出来的钱是不可能有负数的，因此我们只需要穷举第二种和第三种就可以了

    private int helper(int[] nums,int start,int end){
        int[] dp = new int[nums.length+2];
        dp[end+1] = 0;
        for(int i = end;i>=start;i--){
            dp[i] = Math.max(
                    dp[i+2]+nums[i],
                    dp[i+1]
            );
        }
        return dp[start];
    }

    public int rob(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        return Math.max(helper(nums,0,nums.length-2),helper(nums,1,nums.length-1));//是否选择拿第一间房子的钱
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.18.4 树形排列情况

• 这道题是再升级版，要求获取钱的房子是不能有边的。

• 依旧是按照选择的套路来做，如果说我要拿这个房子的钱，那我要走下家的时候，只能走下家的下家

• 如果我不拿这个房子的钱，就可以走下家

    private Map<TreeNode,Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(memo.containsKey(root)){
            return memo.get(root);
        }
        int do_it = root.val
                +(root.left == null ?
                0: rob(root.left.left)+rob(root.left.right))
                +(root.right == null ?
                0: rob(root.right.left) + rob(root.right.right));
        int not_do = rob(root.left)+rob(root.right);
        int res = Math.max(do_it,not_do);
        memo.put(root,res);
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.19 动态规划算法和回溯算法的关系探究

2.19.1 问题引入

• 回溯算法和动态规划都涉及到递归，都涉及到做选择，那么是否存在一种情况，这两种算法是可以互相转化的呢?
• 以一道题目为例进行分析
• 给你输入一个非负整数数组nums和一个目标值target，现在你可以给每一个元素nums[i]添加+或者-，请计算出有几种符号的组合能够使得nums中的元素的和为target?

2.19.2 回溯思路

• 首先我们拿出回溯的基本模板

function backtrack(路径,选择列表){
    if 满足了结束条件{
        result.add(路径)
    	return
    }
    for(选择 in 选择列表){
        做选择
        backtrack(路径,选择列表)
        撤销选择
    }
}
1
2
3
4
5
6
7
8
9
10
11

• 那么对于这道题来说，有以下几个关键点

  • 选择是什么?选择就是对于每一个数字，是给一个加号还是给一个减号
  • 路径是什么?路径就是做选择，产生的不同的符号组合的这个过程
  • 路径如何来表示?其内在表示是每次计算过程，选择符号的不同，而用数据来表示的话就是，余数的大小和数组数字的下标
  • 什么时候满足结束条件?当取数字到达数组的最后一位的时候，就是结束了，结束的时候就需要解算，我们依次传入一个数字，对目标数字进行加减，如果最终得到的余数为0，那么证明是可行的路径

• 根据上述分析可以先编写出代码

    private int res = 0;
    private int[] op = new int[]{1,-1};


    /**
     * 回溯算法:
     * @param nums
     * @param i:代表的是目前要对哪个数字进行加减的置换
     * @param rest:代表的是距离target的程度,当为0的时候,意味着找到了一组可行的解决方案
     */
    private void backtrack(int[] nums,int i,int rest){
        if(i==nums.length){
            if(rest == 0){
                res ++ ;
            }
            return;
        }
        for(int j = 0;j< op.length;j++){
            rest += op[j]*nums[i];
            backtrack(nums,i+1,rest);
            rest -= op[j]*nums[i];
        }
    }

    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums,0,target);
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 分析时间复杂度，这实际上是一个二叉树的遍历问题，因此时间复杂度为O(2^n),n是数组的长度

2.19.2 消除重叠子问题

• 动态规划之所以比暴力算法快，是因为动态规划技巧地消除了重叠子问题
• 如何发现重叠子问题呢?看是否可能出现重复的“状态”，对于递归函数来说，函数参数中会变的参数就是“状态”，对于backtrack函数来说，会变的参数为i和rest

例如:

void backtrack(int i,int rest){
    backtrack(i+1,rest-nums[i]);
    backtrack(i+1,rest+nums[i]);
}
1
2
3
4

如果 nums[i]==0时，上述式框架就变成了

void backtrack(int i,int rest){
    backtrack(i+1,rest);
    backtrack(i+1,rest);
}
1
2
3
4

• 我们容易看出，此处有两个一模一样的backtrack(),这就是重叠子问题，而且只要我们能够找到一个重叠子问题，那么就一定还能找到更多的重叠子问题
• 优化:备忘录

    private int[] op = new int[]{1,-1};
    private Map<String,Integer> memo;
    /**
     * 回溯算法:
     * @param nums
     * @param i:代表的是目前要对哪个数字进行加减的置换
     * @param rest:代表的是距离target的程度,当为0的时候,意味着找到了一组可行的解决方案
     */
    private int backtrack(int[] nums,int i,int rest){
        if(i==nums.length){
            if(rest == 0){
                return 1;
            }
            return 0;
        }
        String key = i+","+rest;
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        int sum = 0;
        for(int j = 0;j< op.length;j++){
            rest += op[j]*nums[i];
            sum+= backtrack(nums,i+1,rest);
            rest -= op[j]*nums[i];
        }
        memo.put(key,sum);
        return sum;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 时间复杂度为状态的组合数(i,rest)，也就是O(N*target)

2.19.3 动态规划解法

• 如果我们将nums划分为两个子集A和B,分别代表着分配+的数和分配-的数，那么它们和target存在以下关系

sum(A)-sum(B) = target;
sum(A) = target+sum(B);
sum(A)+sum(A) = target+sum(B)+sum(A);
2*sum(A)=target+sum(nums);
sum(A) =(target+sum(nums))/2;
1
2
3
4
5

• 由之前的子集划分问题可以知道，这道题可以解读为一道背包问题
• 有一个背包，容量为sum，现在给你N个物品，第i个物品的重量为nums[i-1](注意1<=i<=N)，每个物品只有一个，请问有几种不同的方法能够恰好装满这个包?
• 状态和选择
  • 状态:目前背包的容量和可选择的物品
  • 选择:是否将该物品加入背包
• 定义dp数组
  • dp[i][j] =x:表示若只在前i个物品中选择，而且当前背包的容量为j，则最多有x种方法可以恰好装满背包
• base-case
  • 当没有物品的时候，找不到一种方法使得背包可以被装满，也就是当i=0的时候,dp[i][j]=0
  • 当背包容量为0的时候而且没有东西可以选的时候，这时候选法有且只有一种
  • 所求答案就是dp[N][sum]
• 状态转移方程
  • 如果不把nums[i]算入子集，或者说不把这第i个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态dp[i-1][j]，继承之前的结果
  • 如果把nums[i]算入子集，那么只要看前i-1个物品有几种方法可以装满j-nums[i-1]的重量就可以了
  • 由于dp[i][j]对应的是所有能够装满背包的选择，所以应该要用加法。

    private int helper(int[] nums,int target){//0-1背包问题
        //1.定义dp数组,dp[i][j]:前i个物品和j的背包容量
        int[][] dp = new int[nums.length+1][target+1];
        //2.写出base-case
        //2.1 当i等于0的时候,找不到一组合适的方法
        for(int j=0;j<=target;j++){
            dp[0][j] = 0;
        }
        //2.2 当没有数可以选而且背包容量又是0的时候,这时候才是0,书上写错了
        dp[0][0] =1;
        //3.确定遍历方向,由DP-table可知初始化的是第零行,因此从(1,0)开始遍历到后边即可
        for(int i = 1;i<=nums.length;i++){
            for(int j = 0;j<=target;j++){//注意,凑成0的选法有很多种,我们必须计算出个数,base-case是无法确定的
                if(j-nums[i-1] <0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[nums.length][target];
    }

    public int findTargetSumWays(int[] nums, int target) {
        //sum(A) =(target+sum(nums))/2;
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        int sumADouble = target+sum;//如果是奇数,那么就无法找到一组合适的划分方法,直接返回0
        //如果全部正数的num加起来都到不了target,我还要给它赋值负数呢,这时候怎么可能会有解?
        if( sum < target || sumADouble%2==1 ){
            return 0;
        }
        //注意有可能sum+target会小于0的,我们可以加上绝对值来规避这个问题
        //为什么加上绝对值结果还不变?这是因为我们使用的是加减号这个符号来控制数值，如果减号成立,那么加号也肯定是成立的
        return helper(nums,Math.abs((sum+target)/2));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

    }
    return dp[nums.length][target];
}

public int findTargetSumWays(int[] nums, int target) {
    //sum(A) =(target+sum(nums))/2;
    int sum = 0;
    for (int num : nums) {
        sum+=num;
    }
    int sumADouble = target+sum;//如果是奇数,那么就无法找到一组合适的划分方法,直接返回0
    //如果全部正数的num加起来都到不了target,我还要给它赋值负数呢,这时候怎么可能会有解?
    if( sum < target || sumADouble%2==1 ){
        return 0;
    }
    //注意有可能sum+target会小于0的,我们可以加上绝对值来规避这个问题
    //为什么加上绝对值结果还不变?这是因为我们使用的是加减号这个符号来控制数值，如果减号成立,那么加号也肯定是成立的
    return helper(nums,Math.abs((sum+target)/2));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1