寫在前

矩陣的問題一般需要這樣考慮：當前坐標(row, col)是如何“走”到的。矩陣問題的動態(tài)規(guī)劃即為填表問題。

1.數(shù)組區(qū)間和 （303-易）

題目描述：給定一個整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j（i ≤ j）范圍內元素的總和，包含 i、j兩點。

示例：

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

思路：本題關鍵：若求解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]

思路：關鍵定義dp數(shù)組，dp[i]：表示以A[i]作為結尾的所有等差數(shù)組的子數(shù)組的個數(shù)。故，當A[i] - A[i-1] == A[i-1] - A[i-2]，即A[i]、A[i-1]、A[i-2]構成等差數(shù)列，狀態(tài)轉移方程為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，每個氣球上都標有一個數(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ù)組的邊界，那么就當它是一個數(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ū)間最后一個被戳破的是哪個氣球，最后一個被戳爆的氣球就設置為 k!!!

• dp數(shù)組：假設 dp[i][j] 表示開區(qū)間 (i,j) 內你能拿到的最多金幣
• 狀態(tài)轉移方程：假設你戳中第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ū)間內的索引（代表區(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];
    }
}