写在前
矩阵的问题一般需要这样考虑：当前坐标(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]; } }
