此博文是繼動態(tài)規(guī)劃總結(jié)之后的案例分析

動態(tài)規(guī)劃的代碼很簡潔，基本在20行以內(nèi)。

一維狀態(tài)定義
53 最大子序和
要求元素是連續(xù)的！
一般來說，子序列的遍歷有三種方式：
1.以某個(gè)元素為起始點(diǎn)，形成長度遞增的子序列
2.以某個(gè)元素為終點(diǎn)，形成長度遞增的子序列
3.某序列長度遞增，形成子序列，如長度為1的子序列就是原始序列中的所有元素

狀態(tài)定義：dp[i]為以nums[i]結(jié)尾的連續(xù)子數(shù)組的最大和
狀態(tài)轉(zhuǎn)移方程：dp[i]=max(dp[i-1] + nums[i], nums[i])
狀態(tài)初始化：dp[0]=nums[0]
輸出：dp[i]中最大元素

139 字符串拆分
按照子串長度增加來遍歷字符串的子串
字符串s可以被拆分成子問題 s1 和 s2
指針 i和 j，其中 i 是當(dāng)前字符串從頭開始的子字符串s'的長度，子串以s[i]結(jié)尾；
j是當(dāng)前子字符串s′的拆分位置，拆分成 s'(0,j)和)s′ (j+1,i) 。用下標(biāo) i 來考慮所有從當(dāng)前字符串開始的可能的子字符串。對于每一個(gè)子字符串，我們通過下標(biāo) j 將它拆分成 s1'′ 和 s2′ （注意 i 現(xiàn)在指向 s2'的結(jié)尾）。

狀態(tài)：dp[i]為從首字符到以s[i]結(jié)尾的子串是否可以被空格拆分為多個(gè)在字典中出現(xiàn)的單詞（i既是長度也是子串末尾的索引）
狀態(tài)轉(zhuǎn)移方程：dp[i]的轉(zhuǎn)移關(guān)系，如果dp[i - j]是true并且s[j:i]在wordDict里, 那么dp[i] = true;（分類討論）
狀態(tài)初始化：dp[0]=1，因?yàn)榭兆址偸亲值涞囊徊糠?輸出：dp[n]

198 打家劫舍
不能偷連續(xù)的兩家，與之前的2個(gè)狀態(tài)有關(guān)

狀態(tài)：dp[i]為偷到第i家，最大偷竊金額(包含第i家)
狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i - 2] + nums[i], dp[i-1]);
狀態(tài)初始化：dp[0]=nums[0], dp[1]=max(nums[0], nums[1]);
輸出：dp[n]

264 丑數(shù)ii
序列是固定的，關(guān)鍵是如何生成。dp[i]與三個(gè)狀態(tài)有關(guān)，之前的數(shù)與三個(gè)數(shù)做乘積，dp保存大小按序排列的丑數(shù)，找出下一個(gè)丑數(shù)。

狀態(tài)：dp[i]為第i個(gè)丑數(shù)的值
狀態(tài)轉(zhuǎn)移方程：dp[i]=min(dp[t2]*2,min(dp[t3]*3,dp[t5]*5))
狀態(tài)初始化：dp[0]=1,第一個(gè)丑數(shù)是1
輸出：dp[n]

279 完全平方數(shù)
對于每個(gè)i，它都可以表達(dá)為，存在一個(gè)j，使得i等于i-jj與jj的和，與所有的狀態(tài)都有關(guān)

狀態(tài)：dp[i]為組成i的完全平方數(shù)的最小個(gè)數(shù)
狀態(tài)轉(zhuǎn)移方程：dp[i] = min(dp[i], dp[i - j*j] + 1);
狀態(tài)初始化：dp[i]=INT_MAX
輸出：dp[n]

300 最長上升子序列
dp[i]與之前所有的狀態(tài)都有關(guān)系

狀態(tài)：dp[i]為以nums[i]為結(jié)尾的子序列的最大長度，注意包含nums[i]
狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i], dp[j] + 1)。在索引 i 之前嚴(yán)格小于 nums[i] 的所有狀態(tài)中的最大者 + 1，因?yàn)檫@個(gè)狀態(tài)轉(zhuǎn)移與前面所有的狀態(tài)都有關(guān)系，要找到最大的一個(gè)狀態(tài)
初始化：每個(gè)字符都是長度為1的子序列
輸出：dp中的最大值

322 零錢兌換
完全背包問題，每種物品可以放無限多次。
自底而上和自頂而下兩種方法，動態(tài)規(guī)劃是自底而上。當(dāng)發(fā)現(xiàn)最優(yōu)子結(jié)構(gòu)：對于金額n，減去某個(gè)面額m1后，剩下的金額n-m1還需要所有的面額去湊n-m1,從而形成最優(yōu)子結(jié)構(gòu)。

當(dāng)前狀態(tài)與之前若干種狀態(tài)相關(guān)，這些狀態(tài)通過硬幣面額來獲得。也是要遍歷所有的硬幣面額。

純粹的貪心會出錯(cuò)，因?yàn)樽钕日业降牟⒉灰欢ㄊ亲顑?yōu)解，所以還要dfs進(jìn)行搜索

狀態(tài)：dp[i]湊成總金額i所需的最小的硬幣數(shù)
狀態(tài)轉(zhuǎn)移方程：假如面值是1,2,5，則f(n)=min(f(n-1)+1, f(n-2)+1, f(n-5)+1)
狀態(tài)初始化：dp所有元素取INT_MAX
輸出：dp(n)

338 比特位計(jì)數(shù)
與數(shù)字的奇偶有關(guān)。
奇數(shù)的二進(jìn)制中1的個(gè)數(shù)=它上一位偶數(shù)的二進(jìn)制中1的個(gè)數(shù)+1
偶數(shù)中二進(jìn)制1的個(gè)數(shù)等于這個(gè)偶數(shù)除以2后的數(shù)二進(jìn)制1的個(gè)數(shù),因?yàn)榕紨?shù)的2倍相當(dāng)于左移1位，末尾填0,1的個(gè)數(shù)不變。
當(dāng)前狀態(tài)與之前的某些狀態(tài)有關(guān)，通過奇偶數(shù)二進(jìn)制中含1的個(gè)數(shù)關(guān)系找到相應(yīng)狀態(tài)

狀態(tài):dp[i]為數(shù)字i中含有1的數(shù)目
狀態(tài)轉(zhuǎn)移方程：dp[i]與i的奇偶有關(guān)，i為奇數(shù)時(shí)候，dp[i] = dp[i - 1] + 1;i為偶數(shù)時(shí)，dp[i] = dp[i / 2];
狀態(tài)初始化：dp[0]=0
輸出：dp[n]

343 整數(shù)拆分
狀態(tài)根據(jù)題目問題進(jìn)行定義，很難一下發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移方程。當(dāng)前狀態(tài)與之前的所有狀態(tài)有關(guān)，i拆分為 j 和 i-j，拆分j后dp[i-j]與j不一定誰大，需要比較下，比如2拆分1*1與2相比，i-j就大! 有兩層循環(huán)，內(nèi)層循環(huán)，遍歷之前的狀態(tài)。

狀態(tài)：dp[i]為整數(shù)i拆分后因數(shù)的最大乘積
狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i], max(dp[i-j], i-j) * j);
狀態(tài)初始化：dp[0]=0, dp[1]=1;
輸出：dp[n]

357 計(jì)算各個(gè)位數(shù)不同的數(shù)字個(gè)數(shù)
數(shù)學(xué)的排列組合問題，A_n_m，無放回的抽取，注意首位不能為0
可以計(jì)算個(gè)位，十位，百位，千位的數(shù)字，然后所有的數(shù)相加
當(dāng)前狀態(tài)只與上一個(gè)狀態(tài)有關(guān)系

狀態(tài)：dp[i]為從10^i-1到10^i中有多少個(gè)，各個(gè)位數(shù)不同的數(shù)
狀態(tài)轉(zhuǎn)移方程：dp[i]=dp[i-1]*（11-i）,9*9*8*7*6*5...因?yàn)槊慷嘁晃唬蜁艘粋€(gè)數(shù)
狀態(tài)初始化：dp[0]=1;dp[2]=9
輸出：dp所有元素之和

368 最大整除子集
子集中，所有元素相互能整除，找到這個(gè)最大的子集中的所有的元素，排序后，找到數(shù)組中能整除的最長串。
dp[i]也是與之前所有的狀態(tài)有關(guān)，因?yàn)閚ums[i]可能是在前面某個(gè)序列的后一個(gè)，所以要遍歷之前所有的狀態(tài)
這道題的代碼非常tricky，last[i]數(shù)組記錄到當(dāng)前i元素最短路徑的元素的索引，與A*路徑搜索代碼極其類似，強(qiáng)烈建議查看！

狀態(tài)：dp[i]為以nums[i]結(jié)尾的序列最長長度(該序列中所有元素能相互整除)
狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[j] + 1;
狀態(tài)初始化：dp定義的時(shí)候全部設(shè)置為0
輸出：dp[i]中最大元素，然后根據(jù)最大元素回溯路徑

376 擺動序列
狀態(tài)中dp[i]必須是以元素i結(jié)尾的，才能找到dp[i]與dp[i-1]的關(guān)系，如果是前i個(gè)的話，就需要遍歷所有的元素

狀態(tài)定義：dp[i]，以diff[i](diff為相鄰差數(shù)組)結(jié)尾的擺動子序列最長長度(不是前i個(gè)元素中，擺動子序列最長長度，這種需要遍歷所有狀態(tài))
狀態(tài)轉(zhuǎn)移方程：若 diff[i] × diff[i-1] < 0， 則有 dp[i] = dp[i-1] + 1，表示最長擺動序列的長度加 1。否則dp[i] = dp[i-1]（因?yàn)閚ums[i]和nums[i-1]相同，所以最后一個(gè)元素可以用nums[i]替換nums[i-1]，序列長度不變）
狀態(tài)初始化：dp[i]=2;
輸出：dp[n]

377 組合總數(shù)-iv
與322 零錢兌換類似
當(dāng)前狀態(tài)與之前所有狀態(tài)有關(guān)，這些狀態(tài)通過nums[i]計(jì)算出來，有兩層循環(huán)
自頂而上進(jìn)行dfs搜索是可以的，但是題目沒要求具體的數(shù)字，也可以自底而下進(jìn)行求
難點(diǎn)在于理解dp[0]=1,必須能湊出來整數(shù)，否則有些數(shù)是湊不出來的

狀態(tài)：dp[i]是以nums元素組成正整數(shù) i 的的組合數(shù)目（不是以i去找nums，i是變化的，nums不變）
狀態(tài)轉(zhuǎn)移方程：dp[i]+=dp[i-nums[j]],dp[4]=dp[4-3]+dp[2]+dp[1]，三種之和（通過搜索樹可以看出來）
狀態(tài)初始化：dp[0]=1
輸出：dp[target]

413 等差數(shù)列劃分
相鄰元素，索引之差為1。
以某個(gè)元素結(jié)尾的等差序列數(shù)目是a，下一個(gè)元素的數(shù)目是b，a和b是沒有交集的。所有以元素結(jié)尾的數(shù)目相加，就是整個(gè)數(shù)組的數(shù)目了

狀態(tài)定義：dp[i]對應(yīng)的是以A[i]這個(gè)元素為結(jié)尾的子串中包含的等差數(shù)組的數(shù)目
狀態(tài)轉(zhuǎn)移方程：dp[i]=dp[i-1]+1
狀態(tài)初始化：dp[i]=0
輸出：所有dp元素之和

雙一維狀態(tài)定義
152 乘積最大子序列
要考慮存在負(fù)數(shù)的元素，則最大和最小值會交換，需要兩個(gè)一維dp來分別記錄最大最小值，由于只與前一個(gè)狀態(tài)相關(guān)，可以進(jìn)行空間壓縮

狀態(tài)：dp1[i]是以s[i]結(jié)尾的序列中最大連續(xù)子序列乘積，dp2[i]是以s[i]結(jié)尾的序列中最小連續(xù)子序列乘積
狀態(tài)轉(zhuǎn)移方程：dp1[i] = max(dp1[i-1]*nums[i], nums[i])與dp2[i] = min(dp2[i-1]*nums[i], nums[i]),負(fù)數(shù)乘以負(fù)數(shù)就變成了最大的正數(shù)，當(dāng)前狀態(tài)只與前一個(gè)狀態(tài)有關(guān)
狀態(tài)初始化：dp1[0]=nums[0], dp2[0]=nums[0]
輸出：dp[n]中最大的值

213 打家劫舍ii
是198題的升級版本，家由原來的鏈狀變成了環(huán)裝，偷第一家不能偷最后一家，可以把數(shù)組拆分成兩個(gè)鏈狀，單獨(dú)求，最后求較大的那個(gè)方案。代碼中使用了一個(gè)i，比較tricky！

狀態(tài)：dp1[i]為前i個(gè)房屋中偷第一家能偷盜金額最大值(含第i戶)，dp2[i]為前i個(gè)房屋中不偷第一家能偷盜金額最大值(含第i戶)
狀態(tài)轉(zhuǎn)移方程：dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i - 2])與dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i - 1]);
狀態(tài)初始化：dp[0]=nums[0], dp[1]=max(nums[0], nums[1]);
輸出：max(dp1[n], dp2[n])

309 最佳買賣股票時(shí)機(jī)含冰凍期
股票系列問題之一，需要對狀態(tài)分為兩個(gè)部分。當(dāng)前狀態(tài)與之前兩個(gè)狀態(tài)有關(guān)

狀態(tài)定義：dp[i][0]和dp[i][1]分別代表第i天持有股票和不持有股票的最大收益
狀態(tài)轉(zhuǎn)移方程：hold[i] = max(hold[i - 1], unhold[i - 2] - prices[i]);與unhold[i] = max(hold[i - 1] + prices[i], unhold[i - 1]);
狀態(tài)初始化：hold[0] = -prices[0]; hold[1] = max(-prices[0], -prices[1]);與        unhold[0] = 0; unhold[1] = max(prices[1] - prices[0], 0);
輸出：hold和unhold中較大的值

二維狀態(tài)定義——普通型
62 不同路徑
根據(jù)題目要問的答案，直接定義出狀態(tài)

狀態(tài)：dp[i][j]為起始點(diǎn)到(i,j)的路徑數(shù)目
狀態(tài)轉(zhuǎn)移方程：dp[i][j]=dp[i - 1][j] + dp[i][j - 1]
狀態(tài)初始化：第一行和第一列都為1
輸出：dp[m-1][n-1]，終點(diǎn)坐標(biāo)

63 不同路徑ii
考慮障礙物時(shí)，要對障礙物進(jìn)行處理

狀態(tài)：dp[i][j]為起始點(diǎn)到(i,j)的路徑數(shù)目
狀態(tài)轉(zhuǎn)移方程：dp[i][j]=dp[i - 1][j] + dp[i][j - 1]，此時(shí)要判斷(i,j)是否是障礙物，如果是的話，則不可到達(dá)，手動置為0
狀態(tài)初始化：第一行和第一列都為1，如果有障礙物，則后面的數(shù)都為0
輸出：dp[m-1][n-1]，終點(diǎn)坐標(biāo)

64 最小路徑和
和62題很類似，在地圖中只能朝下或者右走

狀態(tài)：dp[i][j]為起始點(diǎn)到(i,j)的路徑最小和
狀態(tài)轉(zhuǎn)移方程：dp[i][j]=dp[i - 1][j] + dp[i][j - 1]，此時(shí)要判斷(i,j)是否是障礙物，如果是的話，則不可到達(dá)，手動置為0
狀態(tài)初始化：第一行和第一列累加，只有一條路徑
輸出：dp[m-1][n-1]，終點(diǎn)坐標(biāo)

72 編輯距離
dp[i-1][j-1] 表示替換操作，dp[i-1][j] 表示刪除操作，dp[i][j-1] 表示插入操作。
這個(gè)解答非常詳細(xì)的介紹了，https://leetcode-cn.com/problems/edit-distance/solution/zi-di-xiang-shang-he-zi-ding-xiang-xia-by-powcai-3/

狀態(tài)定義：dp[i][j]是word1從0到i位置的字符串轉(zhuǎn)換到word2的從0到j(luò)位置所需的最小步數(shù)
狀態(tài)轉(zhuǎn)移方程：dp[i][j] = dp[i-1][j-1]或dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1,不同的公式與word1[i] 與 word2[j]是否相同
狀態(tài)初始化：dp[0][j]=j,dp[i][0]=i，前者是插入操作，后者是刪除操作
輸出：dp[m][n]

91 解碼方法
和爬樓梯類似，對于連續(xù)的兩個(gè)數(shù)可以分開處理，或者一起處理。要分類討論(分類討論其實(shí)就是用if進(jìn)行邏輯控制)

狀態(tài)定義：dp[i]為從首字符到s[i]的子串的解碼方法數(shù)目
狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：dp[i]=dp[i-1],if單獨(dú)解碼；dp[i]=dp[i-1] + dp[i-2] if聯(lián)合解碼。不是等式而是分類討論或者歸納法
狀態(tài)初始化：dp[0]=0，沒有用到，dp[1]=1,只有一種方法
輸出：dp[n]

120 三角形最小路徑和
有兩種思路，自頂而下和自底而上.注意不是貪心的思想，如果是貪心的思想求出來的結(jié)果是錯(cuò)的,因?yàn)樨澬牡谝淮吻蟪鰜淼慕Y(jié)果不是最優(yōu)的，沒有考慮所有情況
自頂而下

狀態(tài)定義：dp[i][j]表示從頂點(diǎn)到當(dāng)前節(jié)點(diǎn)的最小路徑和
狀態(tài)轉(zhuǎn)移方程：dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
狀態(tài)初始化：dp[0][0]=triangle[0][0]
輸出：dp[n][j]中的最小值

自底而上

狀態(tài)定義：dp[i][j]表示從底到當(dāng)前節(jié)點(diǎn)(i,j)的最小路徑和
狀態(tài)轉(zhuǎn)移方程：dp[i][j] = min(dp[i+1][j-1],dp[i+1][j])+triangle[i][j]
狀態(tài)初始化：dp[n][j]=triangle[n][j]，初始化最后一行為其自身的路徑
輸出：dp[0][0]中的最小值

221 最大正方形
把面積轉(zhuǎn)換成邊長，在matrix上畫圖分析，可以發(fā)現(xiàn)，dp[i][j]與其周圍的三個(gè)狀態(tài)有關(guān)，可以通過畫圖分析出來

狀態(tài)：dp[i][j]為以(i,j)為右下角的最大正方形的邊長(不是面積)
狀態(tài)轉(zhuǎn)移關(guān)系：dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
狀態(tài)初始化：第一行和第一列，元素是1，則dp為1。dp[i][j] = matrix[i][j] - '0'
輸出：dp中最大的元素

304 二維區(qū)域和檢測——矩陣不可變
前綴和的二維版本，其實(shí)關(guān)鍵在于畫圖出來幫助理解狀態(tài)轉(zhuǎn)移方程。當(dāng)前狀態(tài)與之前三個(gè)狀態(tài)有關(guān)。

狀態(tài)定義:dp[i][j]為矩陣matrix中從(0,0)到(i,j)的矩形內(nèi)所有元素之和
狀態(tài)轉(zhuǎn)移方程：sumRegion(row1, col1, row2, col2) = dp[row2][col2] - dp[row2][col1 - 1] - dp[row1 - 1][col2] + dp[row1 - 1][col1 - 1]
狀態(tài)初始化：dp的第一行和列都為0，可以在定義dp的時(shí)候，整個(gè)dp都初始化為0
輸出：dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1];

1143 最長公共子序列
在原有字符后同時(shí)添加一個(gè)字符，求dp[i][j]與dp[i-1][j-1]之間的關(guān)系，如果兩個(gè)字符相同，則dp[i][j] = dp[i-1][j-1] + 1;，
如果不同，那至少要丟棄一個(gè)字符(因?yàn)橐３衷址南鄬π蛄校詴刹煌恢玫南嗤址麃硌a(bǔ)上)，dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
當(dāng)前狀態(tài)dp[i][j]與0···j的所有狀態(tài)，dp[i][0···j]都有關(guān)！

狀態(tài)定義：dp[i][j]表示字符串s1從0到i與字符串s2從0到j(luò)之間的最長公共子序列的長度
狀態(tài)轉(zhuǎn)移方程： dp[i][j] = dp[i-1][j-1] + 1;與dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
狀態(tài)初始化：dp[i][j]=0
輸出：dp[n1][n2]

二維狀態(tài)定義——區(qū)間型
5 最長回文串
狀態(tài)的定義是定義一個(gè)子串的區(qū)間，很難直接發(fā)現(xiàn)。當(dāng)前狀態(tài)與之前所有狀態(tài)有關(guān)，外層循環(huán)是長度，內(nèi)層循環(huán)是起止位置，所有相同長度的子串遍歷完后再遍歷更長長度的子串

狀態(tài)：dp[i][j]表示字符串從s[i]到s[j]是否為回文串，區(qū)間定義
狀態(tài)轉(zhuǎn)移方程：若s[i]==s[j]&&dp[i+1][j-1]==1，則dp[i][j]=1
初始化：二維表中對角線都為1(單個(gè)字符是回文串)，相鄰相同的字符也需要考慮為回文串
輸出：dp[start][max],通過這兩個(gè)變量記錄最長回文串的起止位置

375 猜數(shù)字大小
相對于easy的猜數(shù)字，medium的是不能用二分查找的，因?yàn)檎业降氖轻槍δ硞€(gè)值，計(jì)算的金額是針對某個(gè)值的，題目要求是確保贏這個(gè)游戲，意味著需要足夠金額保證，無論怎么猜(最壞的情況)都會贏
需要動態(tài)規(guī)劃遍歷所有的結(jié)果才知道最壞的情況猜需要的金額
先求長度為1的dp，然后長度為2....最后求長度為n
當(dāng)前狀態(tài)與之前的所有狀態(tài)有關(guān)，有三層循環(huán)，比較復(fù)雜?。?！
可以參考，https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/solution/cai-shu-zi-da-xiao-ii-by-leetcode/

狀態(tài)定義：dp[i][j]，在i到j(luò)區(qū)間中猜對數(shù)字需要的金額
狀態(tài)轉(zhuǎn)移方程：dp(i,j) = min?(pivot+max(dp(i,pivot?1),dp(pivot+1,n))),piovt遍歷所有的i到j(luò)元素
狀態(tài)初始化：dp[i][i] = 0;
輸出：dp[1][n]

416 分割等和子集
0-1背包問題。
去湊j，有個(gè)選擇是要不要用到nums[i]。不用，則dp[i][j] = dp[i-1][j];可能用，則dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]];
j - nums[i]，是指要用i-1個(gè)元素去湊 j 的剩下部分

狀態(tài)：dp[i][j]表示從數(shù)組的 [0, i] 這個(gè)子區(qū)間內(nèi)挑選一些正整數(shù)，每個(gè)數(shù)只能用一次，使得這些數(shù)的和恰好等于 j。
狀態(tài)轉(zhuǎn)移方程：dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
狀態(tài)初始化：關(guān)于dp[0][j]和dp[i][0]的初始化為0
輸出：dp[n][sum/2]

非leetcode題庫1 0-1背包問題
0-1背包，每個(gè)物品最多只能放一次
有一個(gè)背包，他的容量為C(Capacity)?，F(xiàn)在有n中不同的物品，編號為0…n-1，其中每一件物品的重量為w(i)，價(jià)值為v(i)。問可以向這個(gè)背包中盛放哪些物品，使得在不超過背包容量的基礎(chǔ)上，物品的總價(jià)值最大。
對于dp(i,c)，有兩種情況，將第i個(gè)物品加入和直接忽略第i個(gè)物品

狀態(tài)定義：dp(i,j)將前 i 個(gè)物品放進(jìn)容量為 j 的背包，使得價(jià)值最大。
狀態(tài)轉(zhuǎn)移方程： dp[i][j] = max( dp[i-1][j], v[i] + dp[i-1][j-w[i]]);
狀態(tài)初始化：初始化第一列，如果背包能夠放下w[0]，則dp[0][j]=v[0]，其它部分在定義dp的時(shí)候初始化為0
輸出：dp[n-1][C]

TODO：分析初始化dp長度是n還是n+1
dp的長度設(shè)計(jì)是n還是n+1，與狀態(tài)轉(zhuǎn)移方程有關(guān)，如果出現(xiàn)了i-2就得要n+1了

TODO：初始化的賦值，看看是否有規(guī)律