写在前
矩阵的问题一般需要这样考虑：当前坐标(row, col)是如何“走”到的。矩阵问题的动态规划即为填表问题。
1.数组区间和 （303-易）
题目描述：给定一个整数数组 nums，求出数组从索引 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区间范围的元素和，可以用sum[j + 1] - sum[i] ，注：sum[i]为 0 - i-1的累加和。 那么要注意这时sum数组开辟空间【nums.length + 1】，保证sum[i + 1]可以取到。
代码：动态规划
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];
}
}
// 区间和方法入口
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
2.不同路径II （63-中）
题目描述：如果一个至少有三个元素的等差数列。函数要返回数组 A 中所有为等差数组的子数组个数。
示例：
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数组，dp[i]：表示以A[i]作为结尾的所有等差数组的子数组的个数。故，当A[i] - A[i-1] == A[i-1] - A[i-2]，即A[i]、A[i-1]、A[i-2]构成等差数列，状态转移方程为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] // 新的递增子区间
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] // 新的递增子区间
代码：动态规划
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]为等差数列
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，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例：
输入：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
思路：@狗大王，就先别管前面是怎么戳的，你只要管这个区间最后一个被戳破的是哪个气球，最后一个被戳爆的气球就设置为 k!!!
- dp数组：假设 dp[i][j] 表示开区间 (i,j) 内你能拿到的最多金币
- 状态转移方程：假设你戳中第k个气球（第k个气球最后被戳爆），
dp[i][j] = dp[i][k] + val[i]*val[k]*val[j] + dp[k][j]
ps：根据题意我们可以使用辅助数组，并且在数组的首尾添加1,为啥是开区间，我们不能戳中假边界。
代码：动态规划
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表示开区间的长度（对每一个区间长度进行循环）
for (int len = 3; len <= n + 2; len++) {
// i表示区间的左边界，i + len - 1表示区间的右边界
for (int i = 0; i <= n + 2 - len; i++) {
// k表示开区间内的索引（代表区间最后一个被戳破的气球）
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];
}
}
