数据结构算法题目（五）：动态规划问题的一维压缩算法

之前放在数据结构算法题目（二）：回溯、贪心、动态规划与图论略显臃肿，现在单独拎出来，记录了动态规划的一维压缩问题，有一些问题二维解法更加直观（大部分），但是有些解法一维解法更加简便（例如组合总和Ⅴ），而且一维解法性能往往更高，希望能加深理解。

二维解法理解参考上文或卡哥原文，本文基本不会记录从0进行二维递推。

规律

一维化的遍历顺序是有基本规律的，例如遍历顺序是如何的、是否需要记录上一层值，本文涉及的问题主要有以下：

1. 当前值来自左边和正上方，从上到下、从左往右更新，注意第一列初始条件是否适合一维化。（机器人走方格图的不同路径问题）。

2. 当前值来自正上方dp[i-1][j]和左上方dp[i-1][j-n]，例如01背包问题：从上往下、从右往左遍历。

• 为什么01背包是从右往左遍历：一直的写法是遍历种类i，i每循环一次，代表dp[j]更新一次，代表i个物品自由组合，和二维dp数学意义一致；遍历j代表遍历背包容量，要从右往左遍历，是因为j大，代表背包容量大，j较小的值得到的最大价值一定是j值大的最大价值的子集问题。例如j=2和j=4，j=2的最大价值组合，也一定包含在j=4的结果中，如果用j=2推导j=4，就是某个组合被使用了多次，导致结果错误。

3. 完全背包问题

4. 当前值依赖于周围三个值，形成一个正方形图像，再根据遍历的顺序特性，可能某个值会在循环被覆盖，应该考虑变量暂存。（最长子序列问题）

5. 完全背包全排列

不同路径问题

二维机器人走图问题，实在不太适合一维化，灵活性低于二维数组，变化多点就要变更遍历顺序或者引入暂存量。

1. 不同路径

一个机器人位于一个 m x n 网格的左上角。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。

问总共有多少条不同的路径？ #### 二维镇楼

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m+1,vector<int>(n+1)); //m行n列,第0行、第0列无效
        for(int i=1; i<=m; i++){  //从1开始计数
            for(int j=1; j<=n; j++){ //1开始计算
                dp[i][1] = 1;  //第一列为1
                dp[1][j] = 1;  //第一行为1
                if(i>=2&&j>=2)  //其余为左边和上边方法递推
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];

    }
};

一维DP

初始化：二维数组第一行全1、第一列全1，一维投影也是全1，没有冲突。

递推：每个dp数来自左边和上边值，按行更新。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int>dp(n,1);
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[j] = dp[j]+dp[j-1];
            }
        }
        return dp[n-1];
    }
};

2. 不同路径Ⅱ

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

example:输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右

二维镇楼

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0]==1)  //一开始有障碍肯定不可达
            return 0;
        int m = obstacleGrid.size();  //行数
        int n = obstacleGrid[0].size(); //列数
        int dp[m][n];
        dp[0][0] = 1;  //确保一开始无障碍
        for(int i = 1; i<m; i++){
            if(obstacleGrid[i][0]==1||dp[i-1][0]==0) //第一列有障碍记为0，或者前面已经遇到障碍被记0了
                dp[i][0] = 0;
            else
                dp[i][0] = 1;
        }
        for(int j = 1; j<n; j++){
            if(obstacleGrid[0][j]==1||dp[0][j-1]==0) //第一行有障碍，或者前面已经遇到过障碍
                dp[0][j] = 0;
            else
                dp[0][j] = 1;
        }
        for(int i = 1;i<m;i++){  //填充内部
            for(int j = 1; j<n; j++){
                if(obstacleGrid[i][j]==1)  //障碍位置0
                    dp[i][j]=0;
                else    
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];  //其余同样计算
            }
        }
        return dp[m-1][n-1];
    }
};

一维DP

初始化：只能初始化行，当遇到障碍物，障碍物后都是0；列是冲突的，无法确定是0还是1，

递推：必须排除列的递推，恰好排除后能够正确递推（如果列没有被置0，计算dp[1]时总会加入，如果被置0，那么在这行以后的滚动数组计算也不包含dp[0]，恰好能符合题意）。其余递推基本同理。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0]==1)
            return 0;
        
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<int>dp(n);
        dp[0] = 1;
        for(int j=1; j<n; j++){
            if(obstacleGrid[0][j]==1)
                dp[j] = 0;
            else  
                dp[j] = dp[j-1];
        }
        
        for(int i=1; i<m; i++){
            for(int j=0; j<n; j++){
                if(obstacleGrid[i][j]==1)
                    dp[j] = 0;
                else if(j!=0)
                    dp[j] = dp[j]+dp[j-1];
            }
        }
        return dp[n-1];      
    }
};

01背包问题

1. 携带最大价值材料(01背包)

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

example:
输入：
6 1
2 2 3 1 5 2
2 3 1 5 4 3 输出：5

二维DP镇楼

#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
    int m,n;  //种类、空间
    Solution(int m,int n):m(m),n(n){}
    int get_result(vector<int>&space , vector<int>& value){
        vector<vector<int>>dp(m,vector<int>(n+1));
        for(int j=1; j<=n; j++){
            if(space[0]<=j)
                dp[0][j] = value[0];
        }
        
        for(int i=1; i<m; i++){
            for(int j=1; j<=n; j++){
                if(space[i]>j)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-space[i]]+value[i]);
            }
            
        }
        return dp[m-1][n];
    }
};


int main(){
    int m,n;  //种类、空间
    cin>>m>>n;
    
    vector<int>space(m);
    vector<int>value(m);
    
    for(int i=0; i<m; i++){
        cin>>space[i];
    }
    
    for(int i=0; i<m; i++){
        cin>>value[i];
    }
    
    Solution mySolution(m,n);
    cout<<mySolution.get_result(space,value)<<endl;

    return 0;
}

一维DP

初始化：只考虑第一行投影，放space[0]小于j即可，而且没有冲突。

递推：01背包的递推来自上方以及左上方的某值，符合从右向左条件，原因见《规律》，i维度直接去掉即可，因为滚动数组仅仅依赖上一行。

class Solution{
public:
    int m,n;  //种类、空间
    Solution(int m,int n):m(m),n(n){}
    int get_result(vector<int>&space , vector<int>& value){
        vector<int>dp(n+1);
        for(int j=1; j<=n; j++){
            if(space[0]<=j)
                dp[j] = value[0];
        }
        
        for(int i=1; i<m; i++){
            for(int j=n; j>=0; j--){
                if(space[i]>j)     //该三行代码可去除，dp[j]都是不变情况
                    dp[j] = dp[j];
                else
                    dp[j] = max(dp[j],dp[j-space[i]]+value[i]);
            }
        }
        return dp[n];
    }
};

2. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

example:输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。

二维镇楼

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int m = nums.size();  //行数
        int n = accumulate(nums.begin(),nums.end(),0); //数组和
        if(n%2==1)
            return false;  //为单数不可能分割成两个子集
        n /= 2;  //列数
        vector<vector<int>> dp(m,vector<int>(n+1)); //0固定占额外一列
        for(int j = 1; j<=n; j++){
            if(nums[0]<=j)   //j看成是目标和，小于目标和的元素组合都可以加入dp计算
                dp[0][j] = nums[0]; 
        }    
        
        for(int i=1; i<m; i++){
            for(int j=1; j<=n; j++){
                if(nums[i]>j)   //某个元素值本身大于目标和
                    dp[i][j] = dp[i-1][j]; //不加入这个元素
                else //元素值小于要求和
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]); //求最大组合和
            }
        }
        return dp[m-1][n]==n;  //组合和恰好是目标和，说明目标和可达
    }
};

一维DP

同上题：去除i维度、改变j遍历顺序即可。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum%2==1)    
            return false;
        int n = sum/2;
        int m= nums.size();
        vector<int>dp(n+1);    
        for(int j=1; j<=n; j++){
            if(nums[0]<=j)
                dp[j] = nums[0];
        }

        for(int i=1; i<m; i++){
            for(int j=n; j>=0; j--){
                if(nums[i]>j)
                    dp[j] = dp[j];
                else
                    dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[n]==n;
    }
};

3. 最后一块石头的重量II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；

• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

example:输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

二维镇楼

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(),stones.end(),0);
        int m = stones.size();  //行数
        int n = sum/2;  //列数，列数代表最大重量
        vector<vector<int>>dp(m,vector<int>(n+1));

        for(int j = 1; j<=n;j++){  //j代表最大重量，j列元素代表不超过j的最大组合重量
            if(stones[0]<=j)
                dp[0][j] = stones[0];
        }
        
        for(int i=1; i<m; i++){
            for(int j=1; j<=n; j++){
                if(stones[i]>j)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i]);
            }
        }
        return sum - dp[m-1][n] - dp[m-1][n]; //sum - dp[m-1][n]是另一半对应的重量，再减一次表示两个子集的最小差
    }
};

一维DP

仍然是01背包模板：去除i维度、改变j遍历顺序即可。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(),stones.end(),0);
        int m = stones.size();  //行数
        int n = sum/2;  //列数，列数代表最大重量
        vector<int>dp(n+1);

        for(int j = 1; j<=n;j++){  //j代表最大重量，j列元素代表不超过j的最大组合重量
            if(stones[0]<=j)
                dp[j] = stones[0];
        }
        
        for(int i=1; i<m; i++){
            for(int j=n; j>=0; j--){
                if(stones[i]>j)
                    dp[j] = dp[j];
                else
                    dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return sum - dp[n] - dp[n]; //sum - dp[m-1][n]是另一半对应的重量，再减一次表示两个子集的最小差
    }
};

其余问题

最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

example:输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。

二维镇楼

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>>dp(n,vector<int>(n));
        
        for(int i=s.size()-1; i>=0; i--){
            for(int j=i; j<n; j++){
                if(i==j)   //初始化：单个字符长度1回文
                    dp[i][j] = 1;
                else if(s[i]==s[j])  //其余情况长度+2
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]); //i、j不共存
            }
        }
        return dp[0][n-1];
    }
};

一维DP

典型需要保存变量的一维动态规划：dp[i][j]依赖来自三处：分别是dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，也即当前值的下方、左方、和左下方。而且二维推导回文，需要先从下往上、从左至右推导（见题目二的二维推导），因此产生顺序是dp[i+1][j-1]->dp[i+1][j]->dp[i][j-1]->dp[i][j]。因此有：

• 初始化：自身长度1算回文串，i==j就是初始化，也即对角线全部为1，投影到一维数组就是全1。

• 递推：这个理解可能比较绕，见图： 先说结论：涉及三个容易混淆变量：temp、dp[j]、pre，其中temp、dp[j]代表dp[i+1][j]，pre代表dp[i+1][j-1]，dp[j-1]代表dp[i][j-1]，同二维方法一一对应。

解析：我觉得如果单纯使用投影来解释是有点不负责任的，因为恰巧避开了最难理解的部分：

首先temp每次保存的变量，和内循环是没关系的。例如，j=2,temp=dp[2]，内循环j++，temp=dp[3]，dp[3]只在上一次计算dp[i+1][3]时更新过，和dp[2]等内循环更新没什么关系，因此temp、dp[j]代表dp[i+1][j]。

对pre而言，pre在上一次内循环被temp赋值，在下次j++才被使用，因此pre代表dp[i+1][j-1]。

dp[j-1]则和内循环有关系了，会使用到上次内循环的值，例如dp[3]=max(dp[2],dp[3])，dp[2]在刚刚的内循环是被更新过的，同处于一个外循环下，即i是同层的，代表dp[i][j-1]。

代码：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<int>dp(n,1);  //完成i==j初始化

        for(int i=s.size()-1; i>=0; i--){
            int pre = 0;
            for(int j = i+1; j<s.size(); j++){  //i!=j，二者范围不一样
                int temp = dp[j];
                if(s[i]==s[j])   
                    dp[j] = pre+2;
                else
                    dp[j] = max(dp[j-1],dp[j]); 
                pre = temp;
            }
        }
        return dp[n-1];
        
    }
};

降维打击系列

本文主角，记录了一维方法吊打二维算法的题目。

初始化比较复杂的01背包问题

目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

example：输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3

注意一个重要结论（证明、递归解法见跳转）：本问题等效于“在nums中找出目标和为(target+sum(nums)/2)”的所有组合。

二维镇楼

缺点是初始化第一行、列比较复杂。

//问题等效于求新目标和new_target=(目标和+sum）/2，new_target可达，目标和一定可达
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int m = nums.size();
        int n = accumulate(nums.begin(),nums.end(),0);
        if(abs(target) > n)   //例子有target为负的情况
            return 0;
        if((target+n)%2==1)  //target+n不能是奇数
            return 0;
        int new_target = (target + n)/2; //right值
        vector<vector<int>>dp(m,vector<int>(new_target+1));  //因为是非负

        dp[0][0] = 1;//不放物品0恒满足容量0

        //初始化第一行
        if(nums[0] <= new_target)  //重量范围在new_target以内，即j取得到nums[0]
            dp[0][nums[0]] = 1; //容量刚好为num[0]的算一种方法

        //初始化第一列：自由组合含0，直接影响方法数的初始化
        int zero_num = 0;
        for(int i=0; i<m; i++){  //第一列初始化
            if(nums[i]==0)
                zero_num++;  //有0情况翻倍，例如一个0对应2，两个0对应4，3个0对应8
            dp[i][0] = (int)pow(2.0,zero_num); //有0为2的zero_num次方，无0为1
        }
        
        for(int i=1; i<m; i++){  //递推
            for(int j =1; j<=new_target; j++){
                if(nums[i]>j)  //放入物品i超出背包重量
                    dp[i][j] = dp[i-1][j];  //继承
                else  //可以放入
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];  //原来的方法数 + 预留空间的方法数
            }
        }
        return dp[m-1][new_target];
    }
};

一维DP

二维DP中，行和列的初始化都是不能省略的，因为一旦省略，就会以错误的元素去递推，结果一定是错误的。又不想花时间理解初始化原理，又不想递归那么高的复杂度，可以使用一维DP。

初始化：只需要初始化dp[0]=1，即不放入时恰巧容量0，应该认为是一种方法。

递推：递推改变j的遍历顺序，而且递推必须要包含0，因为初始化第一列并不是固定的，0也需要根据递推改变。

从角度2记忆化搜索开始也可以得到相同的一维化代码，感兴趣参考下文，它更自然解析了为什么i需要包含0这个细节。

//问题等效于求新目标和new_target=(目标和+sum）/2，new_target可达，目标和一定可达
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int m = nums.size();
        int n = accumulate(nums.begin(),nums.end(),0);
        if(abs(target) > n)   //例子有target为负的情况
            return 0;
        if((target+n)%2==1)  //target+n不能是奇数
            return 0;
        int new_target = (target + n)/2; //right值
        vector<int>dp(new_target+1);  //因为是非负

        dp[0] = 1;//不放物品0恒满足容量0

        for(int i=0; i<m; i++){  //必须包含0！！
            for(int j =new_target; j>=0; j--){
                if(nums[i]>j)  //放入物品i超出背包重量
                    dp[j] = dp[j];  //继承
                else  //可以放入
                    dp[j] += dp[j-nums[i]];  //原来的方法数 + 预留空间的方法数
            }
        }
        return dp[new_target];
    }
};

角度2：从记忆化搜索至二维DP至一维DP

代码随想录从原理推导二维初始化比较复杂，这个角度做的二维DP初始化也很简单，值得记录。 ##### 记忆化搜索：通过率58/140 背包问题化归子问题：每个数都可以取或者不取，如果取就占背包容量+i-1子问题，不取就是i-1子问题，从这个角度就是dfs，加入记忆化搜索即得：

//问题等效于求新目标和new_target=(目标和+sum）/2，new_target可达，目标和一定可达
class Solution {
public:
    //数组，剩余量、递归位置、记忆化数组（只有i和余量一样，方法数才能被认为可复用）
    int dfs(vector<int>nums, int new_target, int i, vector<vector<int>>&vp){
        if(i<0){  //从最后一个元素考虑是否选择
            if(new_target==0)  //选择完了，刚好凑出目标和就是一种方法
                return 1;
            else  //不是正确方法
                return 0;
        }
        if(vp[i][new_target]!=0)  //记忆化
            return vp[i][new_target];
        if(nums[i]>new_target)  //放不下
            return dfs(nums,new_target,i-1,vp); //i-1子问题
        //放得下，不放+放 方法数叠加
        return vp[i][new_target] = dfs(nums,new_target,i-1,vp)+dfs(nums,new_target-nums[i],i-1,vp);
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if((sum+target)%2==1)
            return 0;
        int m = nums.size();
        int new_target = (sum+target)/2;
        vector<vector<int>>vp(nums.size(),vector<int>(new_target+1));   //记忆化数组
        int result = 0;
        result += dfs(nums,new_target,nums.size()-1,vp);
        return  result;
    }
};

角度2的二维DP（初始化简单）：通过率140/140

从记忆化搜索得到关键公式是：dfs(nums,new_target,i-1,vp)+dfs(nums,new_target-nums[i],i-1,vp)

dfs变动规：用循环代替递归，用数组代替参数，这里需要记录的是i和new_target（余量），记忆化数组就是相同的i和new_target，才能确定方法数。这里的new_target是余量，每次递归的余量都是减少的，因此应该记为j。

因此应该有：dp[i][j] = dp[i-1][j] + dp[i-1][j-num[i]]，当前方法数 = 不选择nums[i]+选择nums[i]。为了避免符号，等效于dp[i+1][j] = dp[i][j] + dp[i][j-nums[i]]。

初始化，记忆化搜索的终止条件为：

if(new_target==0)  //选择完了，刚好凑出目标和就是一种方法
    return 1;
else  //不算正确方法
    return 0;

说明如果j==0&&在算i==0元素，dp[0][0] = 1；

于是代码：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(abs(target)>sum)  //必须
            return 0;
        if((sum+target)%2==1) //必须
            return 0;
        int m = nums.size();
        int new_target = (sum+target)/2;
        vector<vector<int>>dp(m+1,vector<int>(new_target+1));  //因为要算i+1
        dp[0][0] = 1;
        for(int i=0; i<m; i++){  //记忆化搜索的每次递归i==0都是要计算的，因为终止条件是i<0.
            for(int j=0; j<=new_target; j++){
                if(nums[i]>j)  
                    dp[i+1][j] = dp[i][j];  //return dfs(nums,new_target,i-1,vp); //i-1子问题
                else    
                    dp[i+1][j] = dp[i][j] + dp[i][j-nums[i]]; //核心公式
            }
        }
        return  dp[m][new_target];
    }
};

回到角度1的一维DP

按照01背包降维规律：去除上面代码的i维度、改变j遍历顺序，发现和角度1一维DP完全一样，殊途同归了。

完全背包全排列问题

1. 组合总和Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

example:输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

问题分析：递归在第二篇文章给出，本题只能采用非递归算法才可能通过测试用例。使用二维动态规划需要手推递推公式，见Sterina Solutions，一维解法只需结论+背书，简洁得诱人。