ch10-of-programmercarl-1

C++ C 代码随想录背包问题动态规划

刷题

发布日期: 2022-04-18

509. 斐波那契数
- 思路
- 代码
70. 爬楼梯
- 思路
- 代码
746. 使用最小花费爬楼梯
- 思路
- 代码
62.不同路径
- 思路
- 代码
63. 不同路径 II
- 思路
- 代码
343. 整数拆分
- 思路
- 代码
96. 不同的二叉搜索树
- 思路
- 代码
416. 分割等和子集
- 思路
- 代码
1049. 最后一块石头的重量 II
- 思路
- 代码
494. 目标和
- 思路
- 代码
总结

1 斐波那契数

题目链接：509. 斐波那契数

1.1 题目描述

斐波那契数（通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例1:

输入: n = 2
输出: 1
解释: F(2) = F(1) + F(0) = 1 + 0 = 1

示例2:

输入: n = 3
输出: 2
解释: F(3) = F(2) + F(1) = 1 + 1 = 2

示例3:

输入: n = 4
输出: 3
解释: F(4) = F(3) + F(2) = 2 + 1 = 3

1.2 思路

完整代码如下：

Cpp实现

class Solution {
public:
    int fib(int n) {
        if(n < 2) return n;
        int a = 0, b = 1, c;
        for(int i = 2; i <= n; ++i){
            c = b + a;
            a = b;
            b = c;
        }
        return c;
    }
};

C实现

int fib(int n){
    if(n < 2) return n;

    int dp[n+1];
    dp[0] = 0, dp[1] = 1;
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

2 爬楼梯

题目链接：70. 爬楼梯

2.1 题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例1:

输入: n = 2
输出: 2
解释: 有两种方法可以爬到楼顶。

1 阶 + 1 阶

2 阶

示例2:

输入: n = 3
输出: 3
解释: 有两种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶

1 阶 + 2 阶

2 阶 + 1 阶

2.2 思路

到达第i阶有两种办法：由第i-1阶跳一阶，由第i-2阶跳两阶，因此，有F(N) = F(N-1)+F(N-2)，其实就是斐波那契数，只是起始条件不一样，这题的F(0) = 1, F(1) = 1,即跳到第0阶一共有一种办法，即原地不动。

完整代码如下：

class Solution {
public:
    int climbStairs(int n) {
        if(n < 2) return n;
        int a = 1, b = 1, c;
        for(int i = 2; i <= n; ++i){
            c = b + a;
            a = b;
            b = c;
        }
        return c;
    }
};

C实现

int climbStairs(int n){
    if(n <= 2) return n;
    int dp[n+1];
    dp[1] = 1, dp[2] = 2;
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

3 使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯

3.1 题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例1:

输入: cost = [10,15,20]
输出: 15
解释: 你将从下标为 1 的台阶开始。

支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例2:

输入: cost = [1,100,1,1,1,100,1,1,100,1]
输出: 6
解释: 你将从下标为 0 的台阶开始。

支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。

支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。

支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。

支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。

支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。

支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

3.2 思路

创建一个DP数组，然后初始化为0。当我们跳到某个台阶时，需要支付那个台阶的费用cost[i]后可以往上跳1或2个台阶，我们在跳的时候再把费用加进来，因而有下面的状态转移方程：

$dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])$

那起始点为下标0和1任选，那么起点如何处理呢？这里其实就是题目帮你统一了过程，可以直接把起点看作-1，然后往上跳1阶到达下标为0的台阶，或者往上跳2阶到达下标为1的台阶，注意，这一跳是不需要花费的，因而初始化DP为0，然后最后返回dp[n]即可.

完整代码如下：

Cpp 实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int ans = 0, n = cost.size();
        //int dp[n+1];
        //dp[0] = 0, dp[1] = 0;
        int dp0 = 0, dp1 = 0;
        for(int i = 2; i <= cost.size(); ++i){
            int new_dp1 = min(dp1+cost[i-1], dp0+cost[i-2]);
            dp0 = dp1, dp1 = new_dp1;
            //dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp1;
    }
};

C 实现

int minCostClimbingStairs(int* cost, int costSize){
    //下面两种都是动态规划
    
    //时间复杂度O(n), 空间复杂度O(n)
    /*int dp[costSize + 1];
    dp[0] = 0;
    dp[1] = 0;
    for(int i = 2; i <= costSize; i++){
        dp[i] = fmin(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    }
    return dp[costSize];*/

    //时间复杂度O(n), 空间复杂度O(1)
    int prev = 0, cur = 0;
    for(int i = 2; i <= costSize; i++){
        int next = fmin(prev + cost[i-2], cur + cost[i-1]);
        prev = cur;
        cur = next;
    }
    return cur;
}

4 不同路径

题目链接：62. 不同路径

4.1 题目描述

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

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

问总共有多少条不同的路径？

示例1:

输入: m = 3, n = 7
输出: 28

示例2:

输入: m = 3, n = 2
输出: 3

示例3:

输入: m = 7, n = 3
输出: 28

示例4:

输入: m = 3, n = 3
输出: 6

4.2 思路

机器人的移动方向有两个：向下or向右。因此，机器人到达某个格子(x,y)有两种办法：从(x-1,y)向下；从(x,y-1)向右。建立一个dp数组用来存储机器人到达格子(x,y)的路径数, 易得到状态转移方程为：

$dp[x][y] = dp[x-1][y] + dp[x][y-1]$

dp数组的初始化：第0列和第0行都只有一种路径，即一直向下和一直向右。

完整代码如下：

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

C实现

int uniquePaths(int m, int n){
    int dp[m][n];
    memset(dp, 0 , sizeof(dp));
    for(int i = 0; i < m; i++){
        dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
        dp[0][i] = 1;
    }
    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

5 不同路径 II

题目链接：63. 不同路径 II

5.1 题目描述

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

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

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

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

示例1:

输入: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出: 2

示例2:

输入: obstacleGrid = [[0,1],[0,0]]
输出: 1

5.2 思路

思路和上一题一样，只是这一题要额外对当前遍历的格子的状态进行判断，当当前格子(x,y)为1时说明该格子无法到达，因此，dp[x][y]=0；否则跟上一题一样对状态进行更新：

$dp[x][y] = dp[x-1][y] + dp[x][y-1]$

dp数组的初始化：一样也要注意判断格子的状态，当发现第0列上某个格子为1时，则再往下就无法继续到达，该格子及往后格子均置为0，和第0行也类似。

完整代码如下：

Cpp实现

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if(obstacleGrid[0][0] || obstacleGrid[m-1][n-1]) return 0;
        int dp[m][n];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < m; ++i){
            if(obstacleGrid[i][0]){
                break;
            }
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; ++i){
            if(obstacleGrid[0][i]){
                break;
            }
            dp[0][i] = 1;
        }
        for(int r = 1; r < m; ++r){
            for(int c = 1; c < n; ++c){
                if(obstacleGrid[r][c]){
                    continue;
                }
                dp[r][c] = dp[r-1][c]+ dp[r][c-1];
            }
        }
        return dp[m-1][n-1];
    }
};

C实现

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int dp[obstacleGridSize][obstacleGridColSize[0]];
    int rowSize = obstacleGridSize, colSize = obstacleGridColSize[0];
    for(int i = 0; i < colSize; i++){
        if(obstacleGrid[0][i] != 1){
            dp[0][i] = 1;
        }else{
            for(int ii = i; ii < colSize; ii++){
                dp[0][ii] = 0;
            }
            break;
        }
    }
    for(int i = 0; i < rowSize; i++){
        if(obstacleGrid[i][0] != 1){
            dp[i][0] = 1;
        }else{
            for(int ii = i; ii < rowSize; ii++){
                dp[ii][0] = 0;
            }
            break;
        }
    }
    for(int row = 1; row < rowSize; row++){
        for(int col = 1; col < colSize; col++){
            if(obstacleGrid[row][col] == 1){
                dp[row][col] = 0;
            }else{
                dp[row][col] = dp[row][col-1] + dp[row-1][col];
            }
        }
    }
    return dp[rowSize-1][colSize-1];
}

6 整数拆分

题目链接：343. 整数拆分

6.1 题目描述

给定一个正整数 n，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

6.2 思路

将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j);
将 i 拆分成 j 和 i−j 的和，且 i-j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。

完整代码如下：

Cpp实现

class Solution {
public:
    int integerBreak(int n) {
        /*if(n <= 3) return n-1;
        int ans = 0;
        if(n % 3 == 1){
            ans = pow(3, n/3-1) * 4;
        }else if(n % 3 == 2){
            ans = pow(3, n/3) * 2;
        }else{
            ans = pow(3, n/3);
        }
        return ans;*/

        int dp[n+1];
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; ++i){
            dp[i] = 0;
            for(int j = 1; j < i; ++j){
                dp[i] = max(dp[i], max(dp[i-j]*j, (i-j)*j));
            }
        }
        return dp[n];
    }
};

C实现

int getMax(int a, int b, int c){
    return fmax(fmax(a,b),c);
}

int integerBreak(int n){
    if(n==2) return 1;
    int dp[n+1];
    dp[1] = 1;  //n==2
    dp[2] = 2;  //n==3
    for(int i = 3; i <= n; i++){
        dp[i] = 0;
        for(int j = 1; j < i; j++){
            dp[i] = getMax(dp[i], j*dp[i-j], j*(i-j));
        }
    }
    return dp[n];
}

7 不同的二叉搜索树

题目链接：96. 不同的二叉搜索树

7.1 题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例1:

输入: n = 3
输出: 5

示例2:

输入: n = 1
输出: 1

7.2 思路

动态规划，画几个图可以发现：

一个结点的为1
两个结点可以看作先选1为根剩下的就是dp[1]，然后选2为根剩下的也为dp[1];
三个结点，先选1，剩下的其实就是dp[2]，然后选2，剩下的就是dp[1]*dp[1]，再选3，左边的就是dp[2]
四个结点，先选1，有dp[3]个，然后选2，有dp[1]*dp[2], 然后选3，有dp[2]*dp[1]个，最后选4,有dp[3]个
…

总结上边的规律，可以得到：n个结点的二叉搜索树，可以按照根结点的位置，将左右分为两个子树，然后计算两个子树总共的种类和最终就是其本身的种类数。如结点数为5时，根节点选择1，则左子树为结点数为0的子树，右子树为结点数为4的子树；根节点选择2，则左子树为结点数为1的子树，右子树为结点数为3的子树…则有

$dp[5] = dp[0]*dp[4]+dp[1]*dp[3]+dp[2]*dp[2]+dp[3][1]+dp[4]*dp[0]$

因此，有：

$\begin{equation*} \begin{split} dp[i] &= \sum \limits_{j=0}\limits^{j=i-1}dp[j]*dp[i-j-1]\\ &= \sum \limits_{j=1}\limits^{j=i}dp[j-1]*dp[i-j] \end{split} \end{equation*}$

完整代码如下：

Cpp实现

class Solution {
public:
    int numTrees(int n) {
        int dp[n+1];
        dp[0] = 1, dp[1] = 1;
        for(int i = 2; i <= n; ++i){
            dp[i] = 0;
            for(int j = 0; j < i; ++j){
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }
};

C实现

int numTrees(int n){
    int dp[n+1];
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        dp[i] = 0;
        for(int j = 1; j <= i; j++){
            dp[i] += dp[j - 1]*dp[i - j];
        }
    }
    return dp[n];
}

优化

容易发现，上边的计算过程其实是有重复计算的过程，即根节点在小于等于n/2的一边时的种类数是等于根节点在大于等于(n+1)/2+1的种类数，但需要注意，当结点数为奇数时需要特殊处理。因此，我们可以对上边的代码进行优化，优化后的代码如下：

class Solution {
public:
    int numTrees(int n) {
        int dp[n+1];
        dp[0] = 1, dp[1] = 1;
        for(int i = 2; i <= n; ++i){
            dp[i] = 0;
            for(int j = 0; j < i/2; ++j){
                dp[i] += 2*dp[j]*dp[i-j-1];
            }
            if(i % 2) dp[i] += dp[i/2]*dp[i/2];
        }
        return dp[n];
    }
};

8 分割等和子集

题目链接：416. 分割等和子集

8.1 题目描述

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

示例1:

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

示例2:

输入: nums = [1,2,3,5]
输出: false

8.2 思路

01背包问题，物品重量为nums[i]，对应的价值也为nums[i]，而背包容量则是整个数组的加和的一半。这里求背包的容量应该先判断数组加和是否为奇数，若是则直接返回false.

完整代码如下：

Cpp实现

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int n : nums){
            sum += n;
        }
        if(sum%2) return false;
        int dp[nums.size()+1][sum/2 + 1];
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= nums.size(); ++i){
            for(int j = 1; j <= sum/2; ++j){
                if(j >= nums[i-1]){
                    dp[i][j] = max(nums[i-1] + dp[i-1][j-nums[i-1]], dp[i-1][j]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        if(dp[nums.size()][sum/2] == sum/2) return true;
        return false;
    }
};

C实现

bool canPartition(int* nums, int numsSize){
    int sum = 0;
    for(int i = 0; i<numsSize; i++){
        sum += nums[i];
    }
    if(sum%2  != 0) return false;

    int dp[sum/2 + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i<numsSize; i++){
        for(int j = sum/2; j >=0; j--){
            if(j >= nums[i]){
                dp[j] = fmax(dp[j], dp[j-nums[i]]+ nums[i]);
            }
        }
    }   
    if(dp[sum/2] == sum/2) return true;
    return false;
}

9 最后一块石头的重量 II

题目链接：1049. 最后一块石头的重量 II

9.1 题目描述

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

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

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

示例1:

输入: 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]，这就是最优值。

示例2:

输入: stones = [31,26,33,21,40]
输出: 5

9.2 思路

其实就是01背包，将石头分成加和尽可能接近的两堆，因此先遍历数组求整个数组的加和，然后背包容量为加和的一半，求解背包所能装的物品最大价值，这里物品的价值和重量均为stones[i]。最后整个数组的加和减去两倍背包最大价值即为答案。

完整代码如下：

Cpp实现

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i: stones){
            sum += i;
        }
        int dp[sum/2+1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < stones.size(); ++i){
            for(int j = sum/2; j>=stones[i]; --j){
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return sum - 2*dp[sum/2];
    }
};

C实现

int lastStoneWeightII(int* stones, int stonesSize){
    //分成尽可能相等的两堆
    int sum = 0;
    for(int i = 0; i < stonesSize; i++){
        sum += stones[i];
    }
    int dp[sum/2+1];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < stonesSize; i++){
        for(int j = sum/2; j>=stones[i]; j--){
            dp[j] = fmax(dp[j], dp[j-stones[i]]+stones[i]);
        }
    }
    return sum - dp[sum/2]*2;
}

10 目标和

题目链接：494. 目标和

10.1 题目描述

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

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

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

示例1:

输入: 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

示例2:

输入: nums = [1], target = 1
输出: 1

10.2 思路

为获得目标和，由于我们可以添加的符号是+和-，因而可以将获得目标和转换为两个背包的加和，其中一个背包用来添加负号，另一个背包用来添加正好。更进一步的，我们需要考虑其中一个背包即可，只要其中一个背包满足相应的条件，则另一个背包也将必定满足。

先遍历整个数组，求数组加和sum，如果target大于sum或小于-sum，则说明即使数组中全部用相加或相减都无法达到target，因而返回0.
要满足两个背包的加和等于target，我们只需要让其中一个背包的加和为(sum - target)/2,则另一个背包的加和则为(sum + target)/2, 此时两个背包相加即为target，满足题目需求。
创建一个DP数组dp[n+1][(sum - target)/2+1],其含义为前i个数中加和为j的种数。那么，DP数组如何初始化呢？当背包容量为0时，其最大价值为0的种数为1，即不放入任何数字，因而dp[i][0] = 1.
那么DP数组的状态转移方程如何获得呢？考虑dp[i][j]的含义为前i个数中加和为j的种数，它可以由前i-1个数中加和为j转移而来，也可以由前i-1个数中加和为j-nums[i]转移而来，因此，可以得到状态转移方程：

$\begin{equation*} \begin{split} dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] \quad if \quad j \ge nums[i]\\ dp[i][j] = dp[i-1][j] \quad if \quad j < nums[i]\\ \end{split} \end{equation*}$

完整代码如下：

Cpp实现

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int sum = 0;
        for(int i: nums){
            sum += i;
        }
        if(target < -sum || target > sum || (sum - target)%2) return 0;
        int m = (sum-target)/2;
        int dp[n+1][m+1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i <= n; i++){
            dp[i][0] = 1;
        }
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j <= m; ++j){
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]){
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][m];
    }
};

C实现(优化后)

int findTargetSumWays(int* nums, int numsSize, int target){
    int sum = 0;
    for(int i = 0; i<numsSize; i++){
        sum += nums[i];
    }
    if((sum < target)||((sum-target)%2 != 0)){
        return 0;
    }

    int tmp =(sum - target)/2;
    int dp[tmp+1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 0; i<numsSize; i++){
        for(int j = tmp; j>=nums[i]; j--){
            dp[j] += dp[j-nums[i]];
        }
    }
    return dp[tmp];
}

总结

01背包问题求解：

多维数组：物品和背包容量的两个循环先后顺序无影响，当背包容量大于当前遍历的物品的体积时，当前的背包所能装的最大价值就是不选该物品时的价值dp[i-1][j]和选择该物品(容量为当前背包容量)的价值dp[i-1][j-Weight[i]]+Val[i]中的大者；当背包容量小于该物品的体积时，则背包的最大价值就是遍历到上一个物品的等容量背包的价值dp[i-1][j]。具体的模板如下：
```
for(int i = index; i < WeightSize; ++i){
    for(int j = bagMin; j <= bagSize; ++j){
        if(j >= Weight[i]){
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-Weight[i]]+Val[i]);
        }else{
            dp[i][j] = dp[i-1][j];
        }
    }
}
```
滚动数组：通过对上边的模板进行观察可以发现，上一层的数据在当前层的更新时起作用，而再前边的层的数据已经没用了，所以可以在这个地方进行修改，直接将第一维去掉，代码如下：
```
for(int i = index; i < WeightSize; ++i){
    for(int j = bagMin; j <= bagSize; ++j){
        if(j >= Weight[i]){
            dp[j] = max(dp[j], dp[j-Weight[i]]+Val[i]);
        }else{
            dp[j] = dp[j];
        }
    }
}
```
- 但如果直接这样修改，那么背包容量时，会重复将物品i加入背包中，对于01背包，每个物品只有一个，所以需要将背包容量的遍历过程反过来；另外，修改背包的价值更新，观察上边的代码，背包的价值仅在j >= Weight[i]时才会发生改变，因而可以当j < Weight[i]时直接不进行循环。修改后的代码如下：
```
for(int i = index; i < WeightSize; ++i){
    for(int j = bagSize; j >= Weight[i]; ++j){
        dp[j] = max(dp[j], dp[j-Weight[i]]+Val[i]);
    }
}
```
  - 当01背包用来求解最大价值时，dp数组的含义是背包内的最大价值，状态转移方程为： $\begin{equation*} \begin{split} dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+val[i]) \quad if \quad j \ge weight[i]\\ dp[i][j] = dp[i-1][j] \quad if \quad j < weight[i]\\ \end{split} \end{equation*}$
  - 而当用来求解最大种类数时，dp数组的含义为背包中的物品价值为当前背包容量的种类数，其状态转移方程为： $\begin{equation*} \begin{split} dp[i][j] = dp[i-1][j] + dp[i-1][j-weight[i]] \quad if \quad j \ge weight[i]\\ dp[i][j] = dp[i-1][j] \quad if \quad j < weight[i]\\ \end{split} \end{equation*}$