动态规划26
一、LC 509 斐波那契数列问题
基本盘解法(自顶向下) 6-->5-->4...
1、回溯
穷举==抽象成树形结构 回溯==dfs==递归
dfs是O(1)的但是调用的次数取决于二叉树的节点 --> O(2^n)时间复杂度非常高，O(logn)空间复杂度
2、记忆化搜索优化回溯算法
使用的数据结构考虑，键值对存储计算过的值适合使用Map，由于key的值不会超过n，因此也可以使用数组的索引
时间复杂度O(n)，空间复杂度O(n)
符合大脑的思考习惯(自底而上) 0-->1-->2...
1、迭代
时间复杂度O(n)，空间复杂度O(n)
动态规划四步骤
1、状态数组(难点)
2、状态初始化
3、状态转移(难点)
4、return需要的状态值
状态数组空间压缩（面试中可以试试，比较想见到的一种解法）
状态数组-->两个变量
时间复杂度O(n)，空间复杂度O(1)
二、LC 322 零钱兑换
纯回溯 dfs (超时)
回溯剪枝 (超时)
记忆化搜索 (accept)
自底而上DP (accept)
时间复杂度O(n*k)，空间复杂度O(n)，n为硬币的总额，k为硬币种类
该问题无法进行状态压缩，它的状态和前面所有的状态值都相关
三、DP总结
步骤
问题-->穷举-->抽象树形结构-->dfs/回溯-->记忆化搜索-->状态定义+状态转移(自底而上演示or填表法)
特征
1、存在重复子问题
2、无后效性（后面的选择不会影响前面的选择）
3、最优子结构
四、LC 64 最小路径和 方向数组四个方向有点想不明白啥时候使用了？？？
纯回溯 dfs (超时)
记忆化搜索 (accept)
DP
填表法(自底而上)空间复杂度O(n^2)
// 代码实现
public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
int[][] dp = new int[row][col];
// 右下角的元素确定
dp[row - 1][col - 1] = grid[row - 1][col - 1];
// 底部一行
for (int i = col - 2; i >= 0; i--) {
dp[row - 1][i] = dp[row - 1][i + 1] + grid[row - 1][i];
}
// 右侧一列
for (int i = row - 2; i >= 0; i--) {
dp[i][col - 1] = dp[i + 1][col - 1] + grid[i][col - 1];
}
// 其余位置
for (int i = row - 2; i >= 0; i--) {
for (int j = col - 2; j >= 0; j--) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
}
}
return dp[0][0];
}
DP状态数组压缩为一维 空间复杂度O(n)
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 状态定义，dp[i]表示从右下角到第i - 1行的最短路径
int[] dp = new int[n];
// 状态初始化
dp[n - 1] = grid[m - 1][n - 1];
// 状态转移
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i == m - 1 && j != n - 1) { // 最后一行
dp[j] = grid[i][j] + dp[j + 1];
} else if (i != m - 1 && j == n - 1) { // 最后一列
dp[j] = grid[i][j] + dp[j];
} else if (i != m - 1 && j != n - 1) {
dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
}
}
}
// 返回结果
return dp[0];
}
空间优化O(1)
原地实现（同面试中可试试，想通透才能写出来）
五、LC 53 最大子数组之和
迭代穷举所有子数组 Time O(n^3)
双指针
回溯/dfs
DP 二维数组 超出内存限制
dp[i][j]的列索引肯定是大于行索引的，因此dp数组的下半区不会有值。
dp[i][j] 表示子数组 [i, j] 的累加和。
两种状态转移方程
dp[i][j] = dp[i - 1][j] - dp[i - 1][i - 1];
借助对角线元素
dp[i][j] = dp[0][j] - dp[0][i - 1];
借助第一行元素
前缀和解法
不在需要维护dp数组的状态转移。
