动态规划
动态规划的的四个解题步骤：
- 定义参数化的子问题
- 写出子问题的递推关系
- 确定 DP 数组的计算顺序
- 空间优化（可选）
leetcode 53.最大子数组和
leetcode 198.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
示例 3：
输入：[2,1,1,2] 输出：4 解释：偷窃 1 号房屋 (金额 = 2)，偷窃 4 号房屋 (金额 = 2)。 偷窃到的最高金额 = 2 + 2 = 4 。
定义参数化的子问题
原问题是：从全部(n 间)房子中偷窃出最高的金额
那么子问题：从 k 间房子中偷窃出最高的金额，把原问题参数化，能得到子问题，子问题的参数是 k。并且当 k = n 时，子问题又能求出原问题的解
子问题的递推关系
从特殊到一般情况推导，同时确定边界条件
边界条件
- 如果只有 1 间房子，那么能偷窃的最大金额就是第 1 间房子的金额: f(1) = nums[0]
- 如果只有 2 间房子，那么能偷窃的最大金额就是第 1 间房子和第 2 间房子的金额中的最大值: f(2) = Math.max(nums[0], nums[1])
递推关系推导
条件：不能偷相邻的房子
- 如果有 3 间房子，那么偷窃最大金额的搭配是 [偷第 1 间 + 最后 1 间] 或 [偷第 2 间]: f(3) = Math.max(f(1) + nums[2], f(2))
- 如果有 4 间房子，那么偷窃最大金额的搭配是 [偷前 2 间房子的最大值 + 第 4 间] 或 [偷前 3 间房子的最大值]: f(4) = Math.max(f(2) + nums[3], f(3))
- 如果有 10 间房子，那么偷窃最大金额的搭配是 [偷前 8 间房子的最大值 + 第 10 间] 或 [偷前 9 间房子的最大值]: f(10) = Math.max(f(8) + nums[9], f(9))
从列举的这些例子也能大概推导出递推关系：
定义 DP 数组
DP 数组用于存储每一轮遍历的结果，dp[k] 对应子问题 f(k)，同时 dp[k] 会依赖 dp[k-1] 和 dp[k-2]，所以计算的顺序是从小到大遍历
问题解法
public int rob(int[] nums) {
int length = nums.length;
// 数组只有一个元素的话不进入后面的循环，直接返回
if (length == 1) {
return nums[0];
}
// 存储每一个子问题的结果
// 当去到最后一个问题的时候，这个子问题就是总问题
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}空间优化解法
每次使用 dp 数组都是用 i-1 和 i-2 索引，可以使用局部变量来代替，每一轮遍历都更新这两个局部变量
这样就能省去一个数组的空间
public int rob(int[] nums) {
// 用临时变量代替 dp 数组
// 因为每次用到 dp 数组都是前两个和前一个结果
int length = nums.length;
if (length == 1) {
return nums[0];
}
// 当前结果，初始值：第 2 轮结果
int currentResult = Math.max(nums[0], nums[1]);
// 前一轮结果，初始值：第 1 轮结果
int previousResult = nums[0];
for (int i = 2; i < length; i++) {
// 第 3 轮结果 = max(第 1 轮结果 + 第 3 个元素, 第 2 轮结果)
// 计算后，当前结果：第 3 轮结果；前一轮结果：第 2 轮结果
// 第 4 轮结果 = max(第 2 轮结果 + 第 4 个元素, 第 3 轮结果)
// 计算后，当前结果：第 4 轮结果；前一轮结果：第 3 轮结果
int temp = currentResult;
currentResult = Math.max(previousResult + nums[i], currentResult);
previousResult = temp;
}
return currentResult;
}leetcode 121.买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
定义参数化的子问题
原问题：计算的目标是找到第 n 天卖出股票可以得到的最大收益
子问题：
子问题的递推关系
- 问题边界：如果数组只有一个元素，那么无法得到收益，因为只有买入没有卖出
- 寻找最小值：如果要保证收益最大，那么要求买入的价格是 n 天内最低的价格，并且假设第 k 天找到了更低的买入价，在第 k 天之前都不能用这个更低的买入价。所以最小值的寻找是伴随着主遍历而寻找的，不能先遍历寻找最小值，然后再重新遍历寻找最大价格
- 第 k 天卖出股票的最大收益的选择有两个：
- 用第 k 天的股票价格 - 当前寻找到的最低买入价
- 第 k-1 天的最大收益
所以递推关系是：
定义 DP 数组
DP 数组用于存储每一天可以得到的最大股票收益结果，dp[k] 对应子问题 f(k)，同时 dp[k] 会依赖 dp[k-1]，所以计算的顺序是从小到大遍历
问题解法
public int maxProfit(int[] prices) {
// 维护dp数组的同时，也维护最小值
// dp[i] = max(dp[i-1], prices[i]-min)
// 在第i天获得最大的收益是 max(前一天的最大收益, 今天的价格-累计最小值)
int length = prices.length;
if (length <= 1) {
return 0;
}
int min = prices[0];
int[] dp = new int[length];
dp[0] = 0;
for (int i = 1; i < length; i++) {
min = Math.min(min, prices[i]);
dp[i] = Math.max(dp[i - 1], prices[i] - min);
}
return dp[length - 1];
}空间优化解法
因为每次计算 dp[i] 的时候，都只是使用上一轮计算的结果 dp[i-1]，那么其实可以使用一个临时变量来代替，每一轮重新赋值
public int maxProfit(int[] prices) {
int length = prices.length;
if (length <= 1) {
return 0;
}
int min = prices[0];
int result = 0;
for (int i = 1; i < length; i++) {
result = Math.max(result, (prices[i] - min));
min = Math.min(min, prices[i]);
}
return result;
}使用 result 变量来记录每一天计算出来的股票最大收益