《动态规划》刷题笔记
1. 斐波那契数2. 第 N 个泰波那契数3. 爬楼梯4. 使用最小花费爬楼梯5. 打家劫舍6. 打家劫舍 II7. 删除并获得点数8. 跳跃游戏9. 跳跃游戏 II10. 最大子数组和11. 环形子数组的最大和12. 乘积最大子数组13. 乘积为正数的最长子数组长度 TODO14. 最佳观光组合15. 买卖股票的最佳时机16. 买卖股票的最佳时机 II17. 最佳买卖股票时机含冷冻期18. 买卖股票的最佳时机含手续费1. 斐波那契数
题目：509. 斐波那契数
斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中 n > 1给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1示例 2：
输入：n = 3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2
let fib = function (n: number): number {// dp[i] - 第 i 个斐波那契数let dp = new Array(n + 1)dp[0] = 0dp[1] = 1for (let i = 2; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2]return dp[n]};
2. 第 N 个泰波那契数
题目：1137. 第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入：n = 4输出：4解释：T_3 = 0 + 1 + 1 = 2T_4 = 1 + 1 + 2 = 4示例 2：
输入：n = 25输出：1389537
public int tribonacci(int n) {if (n <= 1) return n;// dp[i] - 第 i 个泰波那契数int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;dp[2] = 1;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];}return dp[n];}
3. 爬楼梯
题目：70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶示例 2：
输入：n = 3输出：3解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶
public int climbStairs(int n) {// dp[i] i 阶楼梯爬到楼顶的方法数量int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
4. 使用最小花费爬楼梯
题目：746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]输出：15解释：你将从下标为 1 的台阶开始。- 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]输出：6解释：你将从下标为 0 的台阶开始。- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。- 支付 1 ，向上爬一个台阶，到达楼梯顶部。总花费为 6 。
标准 DP：初始化值为 0
public int minCostClimbingStairs(int[] cost) {// dp[i] - 爬到第 i 个台阶的最小花费int n = cost.length;int[] dp = new int[n + 1];for (int i = 2; i <= n; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n];}
滚动数组优化： DP 数组的值只与前两项有关, 使用两个变量滚动
public int minCostClimbingStairs(int[] cost) {int n = cost.length;int first = 0, second = 0, tmp;for (int i = 2; i <= n; i++) {tmp = second;second = Math.min(first + cost[i - 2], second + cost[i - 1]);first = tmp;}return second;}
初始化方法不同的 DP：使用 cost 数组进行初始化
public int minCostClimbingStairs(int[] cost) {// dp[i] - 爬到第 i 个台阶的最小花费int n = cost.length;int[] dp = new int[n];dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < n; i++) {dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];}return Math.min(dp[n - 1], dp[n - 2]);}
5. 打家劫舍
题目：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 。
标准 DP：
public int rob(int[] nums) {int[] dp = new int[nums.length + 1];dp[0] = 0;dp[1] = nums[0];for (int i = 2; i <= nums.length; i++) {dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);}return dp[nums.length];}
6. 打家劫舍 II
题目：213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]输出：3解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2：
输入：nums = [1,2,3,1]输出：4解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。示例 3：
输入：nums = [1,2,3]输出：3
核心思路：将环拆成两个队列，一个从 0 到 n-1，另一个从 1 到 n
class Solution {public int rob(int[] nums) {if (nums.length == 1) return nums[0];return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),myRob(Arrays.copyOfRange(nums, 1, nums.length)));}public int myRob(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = nums[0];for (int i = 2; i <= n; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return dp[n];}}
7. 删除并获得点数
题目：740. 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]输出：6解释：删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。示例 2：
输入：nums = [2,2,3,3,3,4]输出：9解释：删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。
将这题转化一下就成了 “打家劫舍”：
[2, 2, 3, 3, 3, 4] -> [0, 0, 4, 9, 4]
class Solution {public int deleteAndEarn(int[] nums) {int[] trans = new int[10001];for (int i = 0; i < nums.length; i++) {trans[nums[i]] += nums[i];}return rob(trans);}// 打家劫舍public int rob(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = nums[0];for (int i = 2; i <= n; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return dp[n];}}
8. 跳跃游戏
题目：跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的第一个下标。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2：
输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
不确定这个是不是动规，感觉就是正常的模拟：
public boolean canJump(int[] nums) {// 只有一个下标, 一定可以到达if (nums.length == 1) return true;// 不止一个下标, 且第一步为0, 一定不能到达if (nums[0] == 0) return false;// res[i] 能否到达坐标 iboolean[] res = new boolean[nums.length];res[0] = true; // 初始下标一定能到for (int i = 0; i < nums.length; i++) {// 如果能到达当前下标, 才能继续跳if (!res[i]) continue;// 计算当前能跳到的下标for (int j = 1; j <= nums[i] && i + j < nums.length; j++) {res[i + j] = true;}}// 能否到达最后一个下标return res[nums.length - 1];}
只维护一个能跳到的最远距离：
public boolean canJump(int[] nums) {int k = 0; // 能跳到的最远距离for (int i = 0; i < nums.length; i++) {if (i > k) return false;k = Math.max(i + nums[i], k);}return true;}
9. 跳跃游戏 II
题目：跳跃游戏 II
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums = [2,3,0,1,4]输出: 2
标准的 DP：
public int jump(int[] nums) {if (nums.length == 1) return 0;// dp[i] 跳到 i 位置需要的最少跳跃次数int[] dp = new int[nums.length];Arrays.fill(dp, nums.length + 1); // 填充最大值dp[0] = 0;dp[1] = 1;for (int i = 2; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (j + nums[j] >= i) {dp[i] = Math.min(dp[i], dp[j] + 1);}}}return dp[nums.length - 1];}
优化 DP：
public int jump1(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, nums.length + 1);dp[0] = 0;for (int i = 0; i < nums.length; i++) {for (int j = 1; j <= nums[i]; j++) {if (i + j >= nums.length) {return dp[nums.length - 1];}dp[i + j] = Math.min(dp[i + j], dp[i] + 1);}}return dp[nums.length - 1];}
注：此题最优解应该是贪心
10. 最大子数组和
题目：53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1]输出：1示例 3：
输入：nums = [5,4,-1,7,8]输出：23
标准 DP：
public int maxSubArray(int[] nums) {// dp[i] i 位置的最大子数组和// 也就是 dp[nums.length - 1] 不是最后答案, max{dp[i]} 才是int[] dp = new int[nums.length];dp[0] = nums[0];int max = dp[0];for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);max = Math.max(max, dp[i]);}return max;}
优化 DP：将空间复杂度优化成常量级别（速度也变快了）
public int maxSubArray(int[] nums) {int cur = nums[0], max = cur;for (int i = 1; i < nums.length; i++) {cur = Math.max(cur + nums[i], nums[i]);max = Math.max(max, cur);}return max;}
11. 环形子数组的最大和
题目：918. 环形子数组的最大和
给定一个长度为 n 的环形整数数组nums ，返回 nums 的非空子数组的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是
nums[(i + 1) % n]， nums[i] 的前一个元素是nums[(i - 1 + n) % n]。子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组
nums[i], nums[i + 1], ..., nums[j]，不存在i <= k1, k2 <= j其中k1 % n == k2 % n。示例 1：
输入：nums = [1,-2,3,-2]输出：3解释：从子数组 [3] 得到最大和 3示例 2：
输入：nums = [5,-3,5]输出：10解释：从子数组 [5,5] 得到最大和 5 + 5 = 10示例 3：
输入：nums = [3,-2,2,-3]输出：3解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
暴力做法（会超时）：将数组拼接成 2 个，然后对其中每连续的nums.length个元素去寻找最大子数组和
public int maxSubarraySumCircular(int[] nums) {int[] doubleNums = new int[nums.length * 2];// 拼接数组：[1,2,3] ---> [1,2,3,1,2,3]System.arraycopy(nums, 0, doubleNums, 0, nums.length);System.arraycopy(nums, 0, doubleNums, nums.length, nums.length);// 对拼接后的数组，每 nums.length 个元素找最大子数组和int res = Integer.MIN_VALUE;for (int i = 0; i < nums.length; i++) {res = Math.max(res, maxSubarray(Arrays.copyOfRange(doubleNums, i, i + nums.length)));}return res;}// 子数组的最大和int maxSubarray(int[] nums) {int cur = nums[0], max = cur;for (int i = 1; i < nums.length; i++) {cur = Math.max(cur + nums[i], nums[i]);max = Math.max(max, cur);}return max;}
正常做法：经历循环求得的最大值、不经历循环求得的最大值，两种情况比大小
经历循环求得的最大值 = 原数组的和 - 子数组的最小和（动态规划）不经历循环求得的最大值 = 子数组的最大和（动态规划）
别的地方偷过来的图片，秒懂：
易理解版代码：分别求出数组和、最大子数组和、最小子数组和，分情况讨论
public int maxSubarraySumCircular(int[] nums) {int sum = Arrays.stream(nums).sum(); // 数组和// 情况一：循环, 数组和 - 最小子数组和int max1 = sum - minSubarray(nums);// 情况二：未循环, 最大子数组和int max2 = maxSubarray(nums);// max1 == 0 说明整个数组都是负数return max1 == 0 ? max2 : Math.max(max1, max2);}// 最小子数组和int minSubarray(int[] nums) {int cur = nums[0], min = cur;for (int i = 1; i < nums.length; i++) {cur = Math.min(cur + nums[i], nums[i]);min = Math.min(min, cur);}return min;}// 最大子数组和int maxSubarray(int[] nums) {int cur = nums[0], max = cur;for (int i = 1; i < nums.length; i++) {cur = Math.max(cur + nums[i], nums[i]);max = Math.max(max, cur);}return max;}
优化后的代码：就是将求最大子数组和、最小子数组和、数组和放到一个循环中完成
public int maxSubarraySumCircular(int[] nums) {int sum = nums[0]; // 数组和int minDp = nums[0], min = minDp; // 求子数组的最小和int maxDp = nums[0], max = maxDp; // 求子数组的最大和for (int i = 1; i < nums.length; i++) {// 求子数组的最小和minDp = Math.min(minDp + nums[i], nums[i]);min = Math.min(min, minDp);// 求子数组的最大和maxDp = Math.max(maxDp + nums[i], nums[i]);max = Math.max(max, maxDp);// 求子数组的和sum += nums[i];}// 情况一：经历循环, 最大和 = 数组和 - 最小子数组和int max1 = sum - min;// 情况二：未经历循环, 最大和 = 最大子数组和int max2 = max;// max1 == 0 说明整个数组都是负数return max1 == 0 ? max2 : Math.max(max1, max2);}
12. 乘积最大子数组
题目：152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: nums = [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
相比最大子数组的和，这题主要是多了负数的处理。
如果有了负数，当前的最大乘积有两种情况：
nums[i] 是正数，当前的最大乘积 = 前面的最大乘积 * nums[i]nums[i] 是负数，当前的最大乘积 = 前面的最小乘积 * nums[i]
所以可以维护两个 dp 数组，分别计算前面的 最小乘积 和 最大乘积：
maxDp[i] = Math.max(nums[i], Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]))minDp[i] = Math.min(nums[i], Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]))
比较标准的动态规划写法：（其实 res 已经是将 dp 数组优化掉的结果，最标准的应该还有一个 DP 数组）
public int maxProduct(int[] nums) {int[] maxDp = new int[nums.length];int[] minDp = new int[nums.length];int res = nums[0]; // 最大值maxDp[0] = minDp[0] = nums[0];for (int i = 1; i < nums.length; i++) {maxDp[i] = Math.max(nums[i], Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]));minDp[i] = Math.min(nums[i], Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]));res = Math.max(res, maxDp[i]);}return res;}
将两个 DP 数组优化掉，用 两个变量 来保存 ‘前面的最大乘积’，‘前面的最小乘积’
这里有个细节，需要备份一下 imax，具体看注释
public int maxProduct(int[] nums) {int res = nums[0], imax = 1, imin = 1;for (int i = 0; i < nums.length; i++) {// 需要备份一下 imax, 因为下一行会将 imax 更新成当前的值, 计算 imin 时用的 imax 应当是前面的最大乘积int tempImax = imax;imax = Math.max(nums[i], Math.max(imax * nums[i], imin * nums[i]));imin = Math.min(nums[i], Math.min(tempImax * nums[i], imin * nums[i]));res = Math.max(res, imax);}return res;}
评论区的答案其实是这么来的，并不应该是直接写出来的：（至少我不能）
将上面那个备份 imax 操作再次优化掉（也不能叫优化，两者效率相当，就是换种实现手段）
public int maxProduct(int[] nums) {int max = Integer.MIN_VALUE, imax = 1, imin = 1;for (int i = 0; i < nums.length; i++) {if (nums[i] < 0) {int temp = imax;imax = imin;imin = temp;}imax = Math.max(nums[i], imax * nums[i]);imin = Math.min(nums[i], imin * nums[i]);max = Math.max(max, imax);}return max;}
再附上一种其他思路：从前往后乘找最大，从后往前乘找最大，比较两者的最大
public int maxProduct(int[] nums) {int res = nums[0], max = 1;// 从前往后乘积最大值for (int i = 0; i < nums.length; i++) {max = (max == 0) ? nums[i] : max * nums[i];res = Math.max(max, res);}// 从后往前乘积最大值max = 1;for (int i = nums.length - 1; i >= 0; i--) {max = (max == 0) ? nums[i] : max * nums[i];res = Math.max(max, res);}return res;}
上面的两个循环可以 “优化” 成一个循环：
（为什么 “优化” 加双引号，因为根据测试，速度反而变慢了，原因是指令执行数量反而更多了？？）
public int maxProduct1(int[] nums) {int len = nums.length;// maxF - 从前往后乘的最大值, maxB - 从后往前乘的最大值int res = nums[0], maxF = 1, maxB = 1;for (int i = 0; i < len; i++) {maxF = (maxF == 0) ? nums[i] : maxF * nums[i];maxB = (maxB == 0) ? nums[len - i - 1] : maxB * nums[len - i - 1];res = Math.max(res, Math.max(maxF, maxB));}return res;}
13. 乘积为正数的最长子数组长度 TODO
题目：1567. 乘积为正数的最长子数组长度
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例 1：
输入：nums = [1,-2,-3,4]输出：4解释：数组本身乘积就是正数，值为 24 。示例 2：
输入：nums = [0,1,-2,-3,-4]输出：3解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。示例 3：
输入：nums = [-1,-2,-3,0,1]输出：2解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
这题还存疑。。。。
14. 最佳观光组合
题目：1014. 最佳观光组合
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为
values[i] + values[j] + i - j，也就是景点的评分之和 减去 它们两者之间的距离。返回一对观光景点能取得的最高分。
示例 1：
输入：values = [8,1,5,2,6]输出：11解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11示例 2：
输入：values = [1,2]输出：2
这题最直观做法是两层 for 循环的暴力做法：（这个应该也算 DP 吧）
Java 这么写但是会超时。（但是 JavaScript 不会。。。）
public int maxScoreSightseeingPair(int[] values) {// dp[j] 到 j 为止的观光景点的最高分int[] dp = new int[values.length];for (int j = 1; j < values.length; j++) {// 寻找最大值int tempMax = -1;for (int i = 0; i < j; i++) {tempMax = Math.max(tempMax, values[i] + values[j] + i - j);}dp[j] = Math.max(dp[j - 1], tempMax);}return dp[values.length - 1];}
转换思路：将题目给出的公式中的 i 和 j 分组考虑，会发现其实只有 i 的状态在变化。
（每次遍历时都可以拿到当前的values[j] - j，只需要维护values[i] + i的最大值即可）
// values[i] + values[j] + i - j// 上式等价于 (values[i] + i) + (values[j] -j)// 由于已经确定 i < j// 相当于我们只要遍历 j, 每次能拿到当前的 (values[j] - j)// 同时不停的更新 (values[i] + i) 的最大值即可public int maxScoreSightseeingPair(int[] values) {int maxI = -1, res = -1;for (int j = 1; j < values.length; j++) {// i < j, 所以 i 最多只能维护到 j 的前一位maxI = Math.max(maxI, values[j - 1] + j - 1);res = Math.max(res, maxI + values[j] - j);}return res;}
15. 买卖股票的最佳时机
题目：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。
标准的动态规划：
public int maxProfit(int[] prices) {// dp[i] 在第 i 天卖出股票可以获得的最大利润// 也就是说 dp[i] 不一定大于 dp[i - 1]// 递推结束后再求出 dp[i] 的最大值才是结果int[] dp = new int[prices.length];// min 第 i 天[之前]的股票的最低价格int min = prices[0];for (int i = 1; i < prices.length; i++) {dp[i] = prices[i] - min > 0 ? prices[i] - min : 0;min = Math.min(min, prices[i]); // 更新股票的最低价格}// 求 dp[i] 的最大值return Arrays.stream(dp).max().getAsInt();}
优化时间：一轮循环
public int maxProfit(int[] prices) {// dp[i] 在第 i 天卖出股票可以获得的最大利润int[] dp = new int[prices.length];// min 第 i 天之前的股票的最低价格, res = max(dp[i])int min = prices[0], res = 0;for (int i = 1; i < prices.length; i++) {dp[i] = prices[i] - min > 0 ? prices[i] - min : 0;res = Math.max(res, dp[i]); // 更新最大值min = Math.min(min, prices[i]); // 更新股票的最低价格}return res;}
优化空间：不开辟数组
public int maxProfit(int[] prices) {// min 第 i 天之前的股票的最低价格, res = max(dp[i])int min = prices[0], res = 0;for (int i = 1; i < prices.length; i++) {res = Math.max(res, prices[i] - min); // 更新最大值min = Math.min(min, prices[i]); // 更新股票的最低价格}return res;}
16. 买卖股票的最佳时机 II
题目：122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回 你能获得的最大利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]输出：7解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。示例 2：
输入：prices = [1,2,3,4,5]输出：4解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。总利润为 4 。示例 3：
输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
自己写出来的垃圾模拟代码：（也是贪心的思想，但是代码比较恶心）
public int maxProfit(int[] prices) {// min - 局部的最低股价// max - 当前手持的股票可以获取的最大利润// profit - 已经卖掉拿到的利润int min = prices[0], max = 0, profit = 0;for (int i = 1; i < prices.length; i++) {if (prices[i] >= prices[i - 1]) {// 今日股票价格比昨日的高, 继续手持股票更新利润max = Math.max(max, prices[i] - min);} else {// 今日股票价格低于昨日股票价格, 将昨日股票卖掉profit += max; // 更新目前利润max = 0; // 当前手持股票从利润0开始min = prices[i]; // 从当前开始维护最低股价, 前面的最低价已经没用}}// 最终的利润 = 已经卖掉拿到的利润 + 手持股票可以获取的利润return profit + max;}
贪心理解角度1：当prices[i] > prices[i - 1]则直接卖掉，然后再次开始买入
public int maxProfit(int[] prices) {int res = 0;for (int i = 1; i < prices.length; i++) {if (prices[i] > prices[i - 1]) {res += prices[i] - prices[i - 1];}}return res;}
贪心理解角度2：相当于每天都在做买卖，如果当天利润为正，则加入总利润
public int maxProfit(int[] prices) {int res = 0; // 总利润for (int i = 1; i < prices.length; i++) {int tmp = prices[i] - prices[i - 1];if (tmp > 0) res += tmp;}return res;}
17. 最佳买卖股票时机含冷冻期
题目：309. 最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:
输入: prices = [1]输出: 0
其实总共就 4 种状态，不需要考虑冷冻期：
两种大状态：
未持有股票 今天没有卖出 —dp[i][0]是今天卖出的 —dp[i][1]持有股票 是今天买入的 —dp[i][2]不是今天买入的 —dp[i][3]
public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][4];dp[0][0] = 0; // 不持有股票, 今天没卖出dp[0][1] = 0; // 不持有股票, 今天卖出的dp[0][2] = -prices[0]; // 持有股票, 今天买入的dp[0][3] = -prices[0]; // 持有股票, 非今天买入for (int i = 1; i < prices.length; i++) {// 今天不持股的情况 = 昨天不持股的两种情况的最大值dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);// 今天卖出股票的情况 = 昨天持有的股票的最大值 + 今天的价格dp[i][1] = Math.max(dp[i - 1][2], dp[i - 1][3]) + prices[i];// 今天买入股票的情况：昨天一定没有卖出股票，也没有买入dp[i][2] = dp[i - 1][0] - prices[i];// 今天没有买股票, 却持有股票, 昨天承过来的dp[i][3] = Math.max(dp[i - 1][2], dp[i - 1][3]);}// 最大值一定是处于不持有股票的状态return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);}
18. 买卖股票的最佳时机含手续费
题目：714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2输出：8解释：能够达到的最大利润: 在此处买入 prices[0] = 1在此处卖出 prices[3] = 8在此处买入 prices[4] = 4在此处卖出 prices[5] = 9总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3输出：6
public int maxProfit(int[] prices, int fee) {int[][] dp = new int[prices.length][2];dp[0][0] = -prices[0]; // 第 i 天手上持有股票的最大利润dp[0][1] = 0; // 第 i 天手上没有股票的最大利润for (int i = 1; i < prices.length; i++) {// 今天持股的最大利润 = 昨天持股今天不动 或 昨天不持股今天买入dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);// 今天不持股的最大利润 = 昨天不持股不动 或 昨天持股今天卖出dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);}return dp[prices.length - 1][1];}
如果觉得《《动态规划入门》刷题笔记（更新中）》对你有帮助，请点赞、收藏，并留下你的观点哦！
