狀態(tài)轉(zhuǎn)移方程
1. 最大子序列和-leetcode53
給定一個整數(shù)數(shù)組nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）巫财，返回其最大和咽笼。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6笋熬。
狀態(tài)轉(zhuǎn)移方程：v(i) = max(v(i-1) + num[i], num[i])
解釋：這里為什么不是v(i) = max(v(i - 1) + nums[i] , v(i - 1))十偶？如果這么寫的話菩鲜，有可能v[i]和 v[i - 1]是同一個子序且也不能實現(xiàn)是連續(xù)子序的要求。
2. 打家劫舍-leetcode198
你是一個專業(yè)的小偷惦积，計劃偷竊沿街的房屋接校。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)狮崩，如果兩間相鄰的房屋在同一晚上被小偷闖入蛛勉，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組睦柴，計算你 不觸動警報裝置的情況下 诽凌，一夜之內(nèi)能夠偷竊到的最高金額。
示例 1：
輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) 坦敌，然后偷竊 3 號房屋 (金額 = 3)侣诵。
偷竊到的最高金額 = 1 + 3 = 4 痢法。
示例 2：
輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)杜顺。
偷竊到的最高金額 = 2 + 9 + 1 = 12 财搁。
狀態(tài)轉(zhuǎn)移方程：v(i) = max(v(i-2)+nums[i], v(i-1))
3
4
5
6
7
8
5. 三角形最小路徑和(數(shù)塔問題)-leetcode120
給定一個三角形，找出自頂向下的最小路徑和躬络。每一步只能移動到下一行中相鄰的結(jié)點上尖奔。
相鄰的結(jié)點 在這里指的是 下標(biāo) 與 上一層結(jié)點下標(biāo) 相同或者等于 上一層結(jié)點下標(biāo) + 1 的兩個結(jié)點。
例如穷当，給定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即提茁，2 + 3 + 5 + 1 = 11）。
分析：
在用動態(tài)規(guī)劃考慮數(shù)塔問題時可以自頂向下的分析馁菜，自底向上的計算茴扁。
從頂點出發(fā)時到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策火邓。同樣的道理下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策丹弱。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了铲咨。
所以第一步對第五層的8個數(shù)據(jù)，做如下四次決策：
如果經(jīng)過第四層2蜓洪，則在第五層的19和7中肯定是19纤勒；
如果經(jīng)過第四層18，則在第五層的7和10中肯定是10隆檀；
如果經(jīng)過第四層9摇天，則在第五層的10和4中肯定是10；
如果經(jīng)過第四層5恐仑，則在第五層的4和16中肯定是16泉坐；
經(jīng)過一次決策，問題降了一階裳仆。5層數(shù)塔問題轉(zhuǎn)換成4層數(shù)塔問題腕让，如此循環(huán)決策…… 最后得到1階的數(shù)塔問題。
算法實現(xiàn)：首先利用一個二維數(shù)組data存儲數(shù)塔的原始數(shù)據(jù)（其實我們只使用數(shù)組data一半的空間歧斟，一個下三角矩陣）纯丸，然后利用一個中間數(shù)組dp存儲每一次決策過程中的結(jié)果（也是一個下三角矩陣）。
初始化dp静袖，將data的最后一層拷貝到dp中觉鼻。dp[n][j] = data[n][j] (j = 1, 2, …, n)其中，n為數(shù)塔的層數(shù)队橙。在動態(tài)規(guī)劃過程匯總坠陈，我們有：
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + data[i][j]萨惑，
最后的結(jié)果保存在dp[0][0]中。
對于上面的數(shù)塔仇矾，我們的data數(shù)組如下：
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
而我們的dp數(shù)組如下：
59
50 49
38 34 29
21 28 19 21
19 7 10 4 16
5. 背包問題I-lintcode92
在n個物品中挑選若干物品裝入背包庸蔼，最多能裝多滿？假設(shè)背包的大小為m若未，每個物品的大小為A[i](不可以將物品進行切割)
樣例 1:
輸入: [3,4,8,5], backpack size=10
輸出: 9
樣例 2:
輸入: [2,3,5,7], backpack size=12
輸出: 12
dp[j] = max(dp[j-A[i]] + A[i], dp[j])
6. 背包問題II-lintcode125
有 n 個物品和一個大小為 m 的背包. 給定數(shù)組 A 表示每個物品的大小和數(shù)組 V 表示每個物品的價值.問最多能裝入背包的總價值是多大?
A[i], V[i], n, m 均為整數(shù)你不能將物品進行切分你所挑選的要裝入背包的物品的總大小不能超過 m每個物品只能取一次
樣例 1:
輸入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
輸出: 9
解釋: 裝入 A[1] 和 A[3] 可以得到最大價值, V[1] + V[3] = 9
樣例 2:
輸入: m = 10, A = [2, 3, 8], V = [2, 5, 8]
輸出: 10
解釋: 裝入 A[0] 和 A[2] 可以得到最大價值, V[0] + V[2] = 10
dp[j] = max(dp[j-A[i]]+V[i], dp[j])
dp[i][j]=max{dp[i-1][j-A[i]]+V[i], dp[i-1][j]};
7. 背包問題III
給定n種具有大小 Ai和價值 Vi的物品(每個物品可以取用無限次)和一個大小為 m 的一個背包, 你可以放入背包里的最大價值是多少?
樣例 :
給出四個物品, 大小為 [2, 3, 5, 7], 價值為 [1, 5, 2, 4], 和一個大小為 10 的背包. 最大的價值為 15.
dp[j] = max(dp[j], dp[j - 1], dp[j - A[k]] + V[k])
參考文獻：
[2] https://blog.csdn.net/theonegis/article/details/45801201
