- 一、动态规划
- 1. 定义
- 2. 基本思想和策略
- 3. 解题思路
- 4. 使用情况
- 二、算法笔记
- 509. 斐波那契数
- 1137. 第 N 个泰波那契数
- 70. 爬楼梯
- 746. 使用最小花费爬楼梯
- 198. 打家劫舍
- 213. 打家劫舍 II
- 740. 删除并获得点数
- 55. 跳跃游戏
- 45. 跳跃游戏 II
- 53. 最大子序和
- 918. 环形子数组的最大和
- 152. 乘积最大子数组
- 1567. 乘积为正数的最长子数组长度
- 1014. 最佳观光组合
- 121. 买卖股票的最佳时机
- 122. 买卖股票的最佳时机 II
- 309. 最佳买卖股票时机含冷冻期
- 714. 买卖股票的最佳时机含手续费
动态规划（DP）问题是算法刷题过程中一大类问题，下面是在刷动态规划题目时的一些总结。 一、动态规划 1. 定义
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
2. 基本思想和策略动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
主要是三点：
- 拆分问题。就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现。
关键就是这个步骤：动态规划有一类问题就是从后往前推到。有时候我们很容易知道：如果只有一种情况时，最佳的选择应该怎么做。然后根据这个最佳选择往前一步推导，得到前一步的最佳选择。 - 定义问题状态和状态之间的关系。前面拆分的步骤之间的关系，用一种量化的形式表现出来，类似于高中学的推导公式，因为这种式子很容易用程序写出来,也可以说对程序比较亲和(也就是最后所说的状态转移方程式)。
- 找到最优解。我们应该将最优解保存下来，为了往前推导时能够使用前一步的最优解，在这个过程中难免有一些相比于最优解差的解，此时我们应该放弃，只保存最优解，这样我们每一次都把最优解保存了下来，大大降低了时间复杂度。
- 将原问题分解为子问题。 (注意：1.子问题与原问题形式相同或类似，只是问题规模变小了，从而变简单了；2,子问题一旦求出就要保存下来，保证每个子问题只求解一遍。)
- 确定状态。(状态：在动规解题中，我们将和子问题相关的各个变量的一组取值，称之为一个"状态"。一个状态对应一个或多个子问题所谓的在某个状态的值，这个就是状态所对应的子问题的解，所有状态的集合称为"状态空间"。我的理解就是状态就是某个问题某组变量，状态空间就是该问题的所有组变量。)
另外：整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间。 - 确定一些初始状态(边界条件)的值。 (这个视情况而定，千万别以为就是最简单的那个子问题解。)
- 确定状态转移方程 (这一步和第三步是最关键的 记住"人人为我"递推，由已知推未知。)
- 问题具有最优子结构。
- 无后效性。（一般遇到的求最优解问题都可以用动态规划）
下面是力扣刷题过程中的
509. 斐波那契数斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
示例一：
输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例二：
输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
代码实现：
class Solution {
public int fib(int n) {
if(n <= 1 ) return n;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
1137. 第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例一：
输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4
示例二：
输入：n = 25 输出：1389537
代码实现：
class Solution {
public int tribonacci(int n) {
// if(n <= 1) return n;
// if(n == 2) return 1;
// 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-1] + dp[i-2] + dp[i-3];
// }
// return dp[n];
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int a = 0, b = 1, c = 1;
for (int i = 3; i <= n; i++) {
int d = a + b + c;
a = b;
b = c;
c = d;
}
return c;
}
}
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例一：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例二：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
代码实现：
class Solution {
public int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
746. 使用最小花费爬楼梯
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例一：
输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例二：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
代码实现：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 0;
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];
}
}
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例一：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例二：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
状态转移方程：
// 状态转移方程，偷第i个房间，则金额为前i-2的金额加该房间
// 不偷该房间，则最大金额为前i-1个房间的，故最大金额为两者最大的
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
只有一间房子：dp[0] = nums[0];
只有两间房子：dp[1] = Math.max(nums[0], nums[1]);
代码实现：
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
if(n == 1) return nums[0];
if(n == 2) return Math.max(nums[0], nums[1]);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i = 2; i < n; i++){
// 状态转移方程，偷第i个房间，则金额为前i-2的金额加该房间
// 不偷该房间，则最大金额为前i-1个房间的，故最大金额为两者最大的
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[n-1];
}
}
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例一：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例二：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例三：
输入：nums = [0] 输出：0
分为两种情况：
// 如果偷窃第一间房子，则偷窃范围为0, n - 2；如果偷窃最后一间房子，则偷窃范围为1, n - 1
代码实现：
class Solution {
public int rob(int[] nums) {
// 因为是一个圆，所以不能偷完第一个偷最后一个
int n = nums.length;
if(n == 1) return nums[0];
if(n == 2) return Math.max(nums[0], nums[1]);
// 如果偷窃第一间房子，则偷窃范围为0, n - 2；如果偷窃最后一间房子，则偷窃范围为1, n - 1
return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
public int robRange(int[] nums, int start, int end){
int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
740. 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例一：
输入：nums = [3,4,2] 输出：6 解释： 删除 4 获得 4 个点数，因此 3 也被删除。 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例二：
输入：nums = [2,2,3,3,3,4] 输出：9 解释： 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。 总共获得 9 个点数。
思路：
根据题意，在选择了元素 x 后，该元素以及所有等于 x−1 或 x+1 的元素会从数组中删去。若还有多个值为 x 的元素，由于所有等于 x−1 或 x+1 的元素已经被删除，我们可以直接删除 x 并获得其点数。因此若选择了 x，所有等于 x 的元素也应一同被选择，以尽可能多地获得点数。
记元素 x 在数组中出现的次数为 cx，我们可以用一个数组 sum 记录数组 num 中所有相同元素之和，即 sum[x]=x⋅cx。若选择了 x，则可以获取 sum[x]] 的点数，且无法再选择 x−1 和 x+1。
代码实现：
class Solution {
public int deleteAndEarn(int[] nums) {
int maxVal = 0;
for (int val : nums) {
maxVal = Math.max(maxVal, val);
}
int[] sum = new int[maxVal + 1];
for (int val : nums) {
sum[val] += val;
}
return rob(sum);
}
public int rob(int[] nums) {
int size = nums.length;
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
55. 跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例一：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例二：
输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
思路：
贪心算法：
for循环存储每个位置最远所能达到的位置
right = Math.max(right, i + nums[i]);
如果能达到最后一个元素，则表明可以跳到。
代码实现：
class Solution {
public boolean canJump(int[] nums) {
int right = nums[0]; // 存储最远可达到位置
for(int i = 0; i < nums.length; i++){
if(i <= right){
right = Math.max(right, i + nums[i]);
if(right >= nums.length-1){
return true;
}
}
}
return false;
}
}
45. 跳跃游戏 II
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例一：
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例二：
输入: nums = [2,3,0,1,4] 输出: 2
贪心算法，每次都跳最远距离
求最少的跳跃次数，和Ⅰ相同，首先计算每个位置最远能到达的位置
记录该位置，步数加1.
代码实现：
class Solution {
public int jump(int[] nums) {
int length = nums.length;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]); // 找到所能达到的最远位置
if (i == end) { // end为最远位置，到达则步数加1
end = maxPosition;
steps++;
}
}
return steps;
}
}
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例一：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例二：
输入：nums = [1] 输出：1
示例三：
输入：nums = [-1] 输出：-1
dp[i] 表示以第 i 个数结尾的连续子数组的最大和，找最大的dp[i]
nums[i] += Math.max(nums[i-1], 0)
以 i 结尾的最大子序和等于以 i 结尾的元素加上上一个元素与0的最大值
最大子序和等于更新的res与nums[i]的最大值
代码实现：
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0]; //存储和的最大值
for(int i = 1; i < nums.length; i++){
nums[i] += Math.max(nums[i-1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}
918. 环形子数组的最大和
给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。
在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）
此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], …, C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）
示例一：
输入：[1,-2,3,-2] 输出：3 解释：从子数组 [3] 得到最大和 3
示例二：
输入：[5,-3,5] 输出：10 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例三：
输入：[3,-1,2,-1] 输出：4 解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
分两种情况：
1.最大数组在中间，与最大子序和相同
2.最大数组跨越头尾，两边大中间小，找最小
代码实现：
class Solution {
public int maxSubarraySumCircular(int[] nums) {
//两种情况，第一种最大数组在中间
int dp = nums[0], max = dp, sum = dp, min = 0;
for(int i = 1; i < nums.length; i++){
sum += nums[i]; // 统计数组元素总和
dp = nums[i] + Math.max(dp, 0);
max = Math.max(dp, max);
}
// 第二种情况，最大数组和跨越头尾，两边大中间最小，找最小
dp = nums[0];
for(int i = 1; i < nums.length-1; i++){
dp = nums[i] + Math.min(dp, 0);
min = Math.min(dp, min);
}
return Math.max(sum-min, max);
}
}
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例一：
输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
示例二：
输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
动态规划，但要考虑遇到正负两种情况。
代码实现：
class Solution {
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 tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax * nums[i], nums[i]); // 存储正的最大值
imin = Math.min(imin * nums[i], nums[i]); // 存储负的最小值
max = Math.max(max, imax);
}
return max;
}
}
1567. 乘积为正数的最长子数组长度
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例一：
输入：nums = [1,-2,-3,4] 输出：4 解释：数组本身乘积就是正数，值为 24 。
示例二：
输入：nums = [0,1,-2,-3,-4] 输出：3 解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。 注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
示例三：
输入：nums = [-1,-2,-3,0,1] 输出：2 解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
示例四：
输入：nums = [-1,2] 输出：1
代码实现：
class Solution {
public int getMaxLen(int[] nums) {
int len= nums.length;
int positive =nums[0]>0?1:0;
int negative =nums[0]<0?1:0;
int max = positive;
for(int i = 1 ;i0){
positive++;//接下的数是 正数，直接加1就完事
negative=negative>0?negative+1:0; //负数×正数=负数
// 所以1.只要negetive存在 长度就加一 2.不存在 只有一个正数 负数在i位置长度为0
}
else if(nums[i]<0){
//nums<0 正数×负数 变号->负连续 不管正数是多少 ，往后加1
int newNegative = positive+1;
//nums<0 negative>0 负数×负数 变号->正连续 因为要求正连续 所以把这个值给positive，如果前面没有负数，那么就为0
int newPositive = negative>0?negative+1:0;
positive=newPositive;
negative=newNegative;
}
else{//因为nums=0直接砍断了连续，长度直接变成0
positive=0;
negative=0;
}
max=Math.max(max,positive);//每个地方 都可能最长 所以都要比较一下
}
return max;
}
}
1014. 最佳观光组合
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例一：
输入：values = [8,1,5,2,6] 输出：11 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例二：
输入：values = [1,2] 输出：2
代码实现：
class Solution {
public int maxScoreSightseeingPair(int[] values) {
// 变形为 values[i]+i 和 values[j]-j 两部分，分别求最大值
int left = values[0], res= Integer.MIN_VALUE;
for(int i = 1; i < values.length; i++){
res = Math.max(res, left + values[i] - i); // 更新
left = Math.max(left, values[i] + i); // 更新values[i]+i的最大值
}
return res;
}
}
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例一：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例二：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
代码实现：
class Solution {
public int maxProfit(int[] prices) {
// dp[i]表示前i天获得的最大利润，等于前i-1的最大利润，或第i天卖出的最大利润
// dp[i] = max(dp[i-1], prices[i]- min(prices[0,i-1]))
int profit = 0, cost = Integer.MAX_VALUE;
// profit 更新最大利润， cost更新前i-1最低价格
for(int price : prices){
cost = Math.min(cost, price);
profit = Math.max(profit, price - cost);
}
return profit;
}
}
122. 买卖股票的最佳时机 II
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例一：
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3
示例二：
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例三：
输入: prices = [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
代码实现：
class Solution {
public int maxProfit(int[] prices) {
// 1.贪心算法，只要后一天比前一天大，就把差值加一下
// 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.动态规划
// dp[i][0] 表示第i天交易后手里没有股票的最大利润，dp[i][1] 表示第i天交易后手里持有股票的最大利润
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) 可能是第i-1天没有股票的利润，也可能是第i-1天持有,加上卖出的利润
// dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) 可能是第i-1天持有股票的利润，也可能是第i-1天没有,加上买入的利润
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = - prices[0];
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]);
}
return dp[prices.length-1][0];
}
}
309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例一：
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
代码实现：
class Solution {
public int maxProfit(int[] prices) {
// 动态规划，相比2多了一个冷冻期，冷冻期什么也不能干，冷冻期结束转为不持股状态
if(prices == null || prices.length == 0) return 0;
int[][] dp = new int[prices.length][3]; // 0 不持股，1 持股，2 冷冻期
dp[0][0] = 0; // 不持股
dp[0][1] = - prices[0]; // 持股
dp[0][2] = 0; // 冷冻期
for(int i = 1; i < prices.length; i++){
// 第i天不持股可以从两种状态转移， 1. 第i-1天不持股，第i天仍不买 2.冷冻期结束了，但不买
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]);
// 第i天持股可以从两种状态转移， 1. 第i-1天不持股，分为i-1天是冷冻期，结束后转为不持股状态和第i-1天本身就不持股，然后买
// 2.第i-1天持股，第i天不卖出
dp[i][1] = Math.max(dp[i-1][0] - prices[i], dp[i-1][1]);
// 只有第i-1天卖出，第i天才处于冷冻期
dp[i][2] = dp[i-1][1] + prices[i];
}
// 只有最后一天不持股或者前一天已经卖掉（今天为冷冻期），最大值在二者之间产生
return Math.max(dp[prices.length-1][0], dp[prices.length-1][2]);
}
}
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例一：
输入：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
示例二：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
代码实现：
class Solution {
public int maxProfit(int[] prices, int fee) {
// 动态规划，含手续费的股票交易
// int[][] dp = new int[prices.length][2];
// dp[0][0] = 0; // 不持股
// dp[0][1] = - prices[0] - fee; // 持股
// 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][0];
// // 动态规划，减少状态变量
// int a = 0; // 表示今日手里 没有股票的最大收益。
// int b = Integer.MIN_VALUE; // 表示今日手里 有股票的的最大收益。
// for (int price : prices) {
// // 没有股票，可能昨天就没有，或者昨天有，今天出手了。
// a = Math.max(a, b + price);
// // 有股票，可能昨天就有，或者今天刚买的。
// b = Math.max(b, a - price - fee);
// }
// return a;
// 贪心算法，
int n = prices.length;
int buy = prices[0] + fee;
int profit = 0;
for (int i = 1; i < n; ++i) {
if (prices[i] + fee < buy) {
buy = prices[i] + fee;
} else if (prices[i] > buy) {
profit += prices[i] - buy;
buy = prices[i];
}
}
return profit;
}
}
