寫在前
矩陣的問題一般需要這樣考慮：當(dāng)前坐標(biāo)(row, col)是如何“走”到的羡忘。矩陣問題的動態(tài)規(guī)劃即為填表問題就漾。
1.數(shù)組區(qū)間和 （303-易）
題目描述：給定一個整數(shù)數(shù)組 nums牧挣，求出數(shù)組從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和系冗，包含 i淹仑、j兩點空闲。
示例：
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
思路：本題關(guān)鍵：若求解i - j區(qū)間范圍的元素和令杈，可以用sum[j + 1] - sum[i] ，注：sum[i]為 0 - i-1的累加和碴倾。 那么要注意這時sum數(shù)組開辟空間【nums.length + 1】逗噩，保證sum[i + 1]可以取到。
代碼：動態(tài)規(guī)劃
private int[] sums;
public NumArray(int[] nums) {
sums = new int[nums.length + 1];
for (int i = 1; i <= nums.length; ++i) {
sums[i] = sums[i - 1] + nums[i - 1];
}
}
// 區(qū)間和方法入口
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
2.不同路徑II （63-中）
題目描述：如果一個至少有三個元素的等差數(shù)列跌榔。函數(shù)要返回數(shù)組 A 中所有為等差數(shù)組的子數(shù)組個數(shù)异雁。
示例：
A = [0, 1, 2, 3, 4]
return: 6
[0, 1, 2],
[1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3, 4],
[ 1, 2, 3, 4],
[2, 3, 4]
思路：關(guān)鍵定義dp數(shù)組，dp[i]：表示以A[i]作為結(jié)尾的所有等差數(shù)組的子數(shù)組的個數(shù)僧须。故纲刀，當(dāng)A[i] - A[i-1] == A[i-1] - A[i-2]，即A[i]担平、A[i-1]示绊、A[i-2]構(gòu)成等差數(shù)列，狀態(tài)轉(zhuǎn)移方程為dp[i] = dp[i-1] + 1暂论。例
dp[2] = 1
[0, 1, 2]
dp[3] = dp[2] + 1 = 2
[0, 1, 2, 3], // [0, 1, 2] 之后加一個 3
[1, 2, 3] // 新的遞增子區(qū)間
dp[4] = dp[3] + 1 = 3
[0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一個 4
[1, 2, 3, 4], // [1, 2, 3] 之后加一個 4
[2, 3, 4] // 新的遞增子區(qū)間
代碼：動態(tài)規(guī)劃
public int numberOfArithmeticSlices(int[] A) {
int n = A.length;
int ret = 0;
int[] dp = new int[n];
for (int i = 2; i < n; ++i) {
// A[i]面褐、A[i-1]、A[i-2]為等差數(shù)列
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
ret += dp[i];
}
}
return ret;
}
3.戳氣球 （312-中）
題目描述：有 n 個氣球取胎，編號為0 到 n - 1展哭，每個氣球上都標(biāo)有一個數(shù)字湃窍，這些數(shù)字存在數(shù)組 nums 中。
現(xiàn)在要求你戳破所有的氣球匪傍。戳破第 i 個氣球您市，你可以獲得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬幣。 這里的 i - 1 和 i + 1 代表和 i 相鄰的兩個氣球的序號役衡。如果 i - 1或 i + 1 超出了數(shù)組的邊界茵休，那么就當(dāng)它是一個數(shù)字為 1 的氣球。
求所能獲得硬幣的最大數(shù)量映挂。
示例：
輸入：nums = [3,1,5,8]
輸出：167
解釋：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
思路：@狗大王泽篮，就先別管前面是怎么戳的盗尸，你只要管這個區(qū)間最后一個被戳破的是哪個氣球柑船，最后一個被戳爆的氣球就設(shè)置為 k!!!
- dp數(shù)組：假設(shè) dp[i][j] 表示開區(qū)間 (i,j) 內(nèi)你能拿到的最多金幣
- 狀態(tài)轉(zhuǎn)移方程：假設(shè)你戳中第k個氣球（第k個氣球最后被戳爆），
dp[i][j] = dp[i][k] + val[i]*val[k]*val[j] + dp[k][j]
ps：根據(jù)題意我們可以使用輔助數(shù)組泼各，并且在數(shù)組的首尾添加1,為啥是開區(qū)間鞍时，我們不能戳中假邊界。
代碼：動態(tài)規(guī)劃
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] tmp = new int[n + 2];
tmp[0] = 1;
tmp[n + 1] = 1;
for (int i = 0; i < n; i++) {
tmp[i + 1] = nums[i];
}
int[][] dp = new int[n + 2][n + 2];
// len表示開區(qū)間的長度（對每一個區(qū)間長度進行循環(huán)）
for (int len = 3; len <= n + 2; len++) {
// i表示區(qū)間的左邊界扣蜻，i + len - 1表示區(qū)間的右邊界
for (int i = 0; i <= n + 2 - len; i++) {
// k表示開區(qū)間內(nèi)的索引（代表區(qū)間最后一個被戳破的氣球）
int j = i + len - 1;
for (int k = i + 1; k < j; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i][k] + tmp[i]*tmp[k]*tmp[j] + dp[k][j]);
}
}
}
return dp[0][n + 1];
}
}
