學(xué)算法好痛苦，完全是對我智力的一次次折磨，看了好多博客，對二維dp數(shù)組的理解都是直接搬了代碼隨想錄，搬了隨想錄又沒詳細解釋，大家都是一眼看懂的嗎，好吧（）

一、對二維dp數(shù)組的理解

背景

1. 如果有一個容量為j的這樣的背包——一個獨立的，容量為j的背包。(沒把它理解為“剩余容量”)
2. 對于這個背包，可以從編號為0至i的物品里任意挑，挑幾個無所謂，挑多重的無所謂
3. 計算第二步挑選的價值，取所有挑選中使整個背包價值最大的這次挑選，將最大的價值記為dp[i][j]
4. 根據(jù)前三步，整體的dp[n][m]就是一個n+1行、m+1列的表格。取其中的一格看，比如第i行第j列的dp[i][j]，它的含義為：對于容量為j的背包，編號0-i的物品隨便挑，背包最大價值為多少。下面，我們詳細說一下dp[i][j]的遞推公式。

dp[i][j]的推導(dǎo)

1. dp[i][j]的推導(dǎo)看起來很難，因為要對i+1個物品每個物品0~i都選擇放或者不放，那么就有$2^{i+1}$次挑選
2. 但是實際情況下，求dp[i][j]只需要考慮第i個物品的放與不放，也就是對于這個格子只要考慮對于1個物品的2次挑選方式（選與不選）+1次查表（查表——我們遍歷表格dp[n][m]的時候已經(jīng)填寫了在dp[i][j]之前的格子，之前的最優(yōu)挑選查找表格即可。）
3. 為什么可以通過1次查表簡化前$2^i$次挑選？

• 首先，不考慮背包容量，如果我們需要dp[i][j]是價值最大的，那么可以分兩種情況：在第三步選定“這次挑選”的時候，dp[i][j]【情況1：使整個背包價值最大的這次挑選含第i個物品】，【情況2：使整個背包價值最大的這次挑選不含第i個物品】，那么合起來

dp[i][j]=max{含第i個物品的挑選的背包價值，不含第i個物品的挑選的背包價值}

• 其次，再考慮上背包容量，
  ①含第i個物品的挑選的背包價值：由于第i個物品占一定的容量，此時需要調(diào)整第0到第i-1個物品的挑選方式。因為需要預(yù)留第i個物品的容量，所以對于第0到第i-1個物品，最多只能j-weight[i]的容量，價值為查表得到的dp[i-1][j-weight[i]];對于第i個物品，確定是放，所以再加上它本身的價值value[i]。
  ②不含第i個物品的挑選的背包價值：與dp[i-1][j]相同。因為這種情況等于是從容量為j的背包里選，但只從第0到第i-1個物品里挑。

dp[i][j]
=max{含第i個物品的挑選的背包價值,同樣大小的背包不含第i個物品的挑選}
=max{dp[i-1][j],dp[i-1][j-weight[i]]+value[i]}

備注：①中還需要判斷 j 是否小于 weight[i]，不然j-weight[i]就變成負值，無法成為數(shù)組下標(biāo)。

二、優(yōu)化：滾動一維數(shù)組

如不考慮中間狀態(tài)，可優(yōu)化空間復(fù)雜度，僅使用j+1個空間，而非（i+1）*(j+1)個。

需要逆序（遍歷 j 時），以保證從后往前的時候前面的初始化是沒動的，不然dp[j-weight[i]]的計算會用到前面已經(jīng)加過value[i]的元素，從而再加一個。這個看代碼隨想錄手動推一遍還是比較簡單，故不細說。

例1 LeetCode 416. 分割等和子集

由于看了之前的0-1背包，被困住了思路，老是覺得0-1背包是求的一堆元素的“最大值”，而等和子集求的是一堆元素等于某個值的情況，思想上感覺不一樣。知道回溯法不配合剪枝肯定不行（200個num，$2^{200}$）
然后隔了一天看了別人沒學(xué)代碼隨想錄的題解，發(fā)現(xiàn)其實很簡單，因為我誤認(rèn)為我這里的dp[][]里存放的是和，或者一個特定的值什么的，其實不是，就是單純的布爾變量，1，或者0。dp[i][j]代表：i個元素，任意選擇是否"可"為j?可->1，不可->0，就這么簡單。

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
           //元素和相等——>數(shù)字集合的和等于1/2 sum
        if (accumulate(nums.begin(), nums.end(), 0) % 2 != 0 || nums.size() == 1)
            return 0;

        int target = accumulate(nums.begin(), nums.end(), 0) / 2;
        vector <vector<int>> dp(nums.size(), vector<int>(target + 1,0));
        //vector<vector<int>> vec(row, vector<int> (col,0)); -- 用 0 來初始化二維vector

        for (int i = 0; i < nums.size(); ++i) {
            dp[i][0] = 1;//均有方法可使得和為0
        }

        for (int j = 1; j <= target; ++j) {
            dp[0][j] = (j == nums[0]);
        }
        for (int i = 1; i < nums.size(); ++i)
        {
            for (int j = 1; j <= target; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j - nums[i] >= 0)
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
            }
            if (dp[i][target] == 1) 
                return 1;
        }
        return 0;
    }
};

notes

第一，vector二維數(shù)組的初始化問題。如果不手動初始化的話，似乎vector只會初始化一行，所以需要使用vector<vector<int>> vec(row, vector<int> (col,0)); -- 用 0 來初始化二維vector這一行代碼，前面是row的數(shù)量，后面是col的數(shù)量。
第二，dp的初始化。第一次寫的時候，初始化很想當(dāng)然，理清思路以后初始化還是比較簡單的。文章來源地址http://www.zghlxwxcb.cn/news/detail-470641.html

到了這里，關(guān)于01背包問題-遞推公式的自我理解與LeetCode 416. 分割等和子集的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！