- 1. 动态规划简介
- 2. 动态规划五步曲
- 3. 动态规划基础题目必须 掌握
- 剑指 Offer 10- I. 斐波那契数列 简单">剑指 Offer 10- I. 斐波那契数列 简单
- 70. 爬楼梯 简单">70. 爬楼梯 简单
- 746. 使用最小花费爬楼梯 简单">746. 使用最小花费爬楼梯 简单
- 62. 不同路径 中等">62. 不同路径 中等
- 64. 最小路径和 中等">64. 最小路径和 中等
- 96. 不同的二叉搜索树 中等">96. 不同的二叉搜索树 中等
- 1262. 可被三整除的最大和 中等">1262. 可被三整除的最大和 中等
- 152. 乘积最大子数组 中等">152. 乘积最大子数组 中等
- 4. 背包问题必须 掌握
- 416. 分割等和子集 中等">416. 分割等和子集 中等
- 1049. 最后一块石头的重量 II 中等">1049. 最后一块石头的重量 II 中等
- 494. 目标和 中等">494. 目标和 中等
- 518. 零钱兑换 II 中等">518. 零钱兑换 II 中等
- 322. 零钱兑换 中等">322. 零钱兑换 中等
- 377. 组合总和 Ⅳ 中等">377. 组合总和 Ⅳ 中等
- 279. 完全平方数 中等">279. 完全平方数 中等
- 5. 打家劫舍必须 掌握
- 198. 打家劫舍 中等">198. 打家劫舍 中等
- 337. 打家劫舍 III 中等">337. 打家劫舍 III 中等
- 6. 股票问题必须 掌握
- 7. 子序列问题必须 掌握
- 300. 最长递增子序列 中等">300. 最长递增子序列 中等
- 673. 最长递增子序列的个数 中等">673. 最长递增子序列的个数 中等
- 674. 最长连续递增序列 简单">674. 最长连续递增序列 简单
- 718. 最长重复子数组 中等">718. 最长重复子数组 中等
- 1143. 最长公共子序列 中等">1143. 最长公共子序列 中等
1. 动态规划简介
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式 [5] 。
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，
在关于贪心算法，你该了解这些！(opens new window)中我举了一个背包问题的例子。
例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。
所以贪心解决不了动态规划的问题。
2. 动态规划五步曲
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
3. 动态规划基础题目必须 掌握
剑指 Offer 10- I. 斐波那契数列 简单
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
题解概要：
- 使用动态规划五步分析法。
- 明确dp的含义：dp（n）代表斐波那契数列的第N项。
- 递推公式：dp[n] =dp[n-1]+dp[n-2]
- 初始值：dp[0] = 0,dp[1] = 1
- 遍历顺序：从小到大。
举例：dp[2] = dp[1] + dp[0] = 1
dp[3]= dp[2] + dp[1] = 2
代码：
func fib(n int) int {if n < 2{return n}dp := make([]int,n+1)dp[1] = 1for i := 2;i <= n;i++{dp[i] = (dp[i-1] + dp[i-2])% 1000000007}return dp[n]}
70. 爬楼梯 简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
题解概要：
- 使用动态规划五步分析法。
- 明确dp的含义：dp[n]代表爬到n阶的方法数。
- 递推公式：dp[n] =dp[n-1]+dp[n-2]。因为每次都可以爬1或2个台阶。所以可以在台阶n-2时爬两个台阶，也可以在台阶n-1时,爬一个台阶。爬上台阶n的方法数就为 dp[n] = dp[n-1] + dp[n-2]
- 初始值：dp[0] = 1,dp[1] = 1 因为是方法数，可以选择从台阶0开始，也可以选择从台阶1开始。
- 遍历顺序：从小到大。
举例：dp[2] = dp[1] + dp[0] = 2
dp[3]= dp[2] + dp[1] = 3
dp[4] = dp[3] + dp[2] = 5
代码：
func climbStairs(n int) int {if n < 2{return 1}dp := make([]int,n+1)dp[0] = 1dp[1] = 1for i := 2; i <= n;i++{dp[i] = dp[i-1] + dp[i-2]}return dp[n]}
746. 使用最小花费爬楼梯 简单
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
提示：
cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据，范围为 [0, 999] 。
题解概要：
图解
- 使用动态规划五步分析法。
- 明确dp的含义：dp[n]代表爬到n层的最低花费。其中，n=len(cost)+1。
- 递推公式：dp[i] =min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。想爬上台阶i，可以选择在台阶i-1时爬一层台阶，花费cost[i-1],也可以在台阶i-2时爬两层台阶，花费cost[i-2]。两者取最小值。
- 初始值：dp[0] = 0,dp[1] = 0 。如上图所示，我们一开始就可以到达dp[1]的位置。因此,dp[0]和dp[1]都是0。
- 遍历顺序：从小到大。
dp[2] = min(cost[0],cost[1]) = 10
代码： ```go func minCostClimbingStairs(cost []int) int { dp := make([]int,len(cost)+1) for i := 2;i < len(dp);i++{dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
} return dp[len(dp)-1] }
func min(a,b int)int{ if a < b{ return a } return b }
---<a name="EVXfP"></a>#### [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/) 简单输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。<br />要求时间复杂度为O(n)。**示例 1：**<br />输入: nums = [-2,1,-3,4,-1,2,1,-5,4] <br />输出: 6 <br />解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。**提示：**- 1 <= arr.length <= 10^5- -100 <= arr[i] <= 100**题解概要：**1. 使用动态规划五步分析法。1. 明确dp的含义：dp[n]代表以n结尾子数组和的最大值。1. 递推公式：dp[i] =max(dp[i-1],0)+nums[i]。由于dp数组的含义，以i结尾的子数组和一定包含nums[i]。若dp[i-1] > 0，则最大子数组的和需包含dp[i-1],若dp[i-1] < 0,则舍弃dp[i-1],只取nums[i]。1. 初始值：dp[0] = nums[0]1. 遍历顺序：从小到大。1. 举例：dp[0] = -2dp[1] = 1 //舍弃dp[0],取nums[1]<br /> dp[2] = -2 //dp[1] + nums[2]<br /> <br />**代码：**```gofunc maxSubArray(nums []int) int {dp := make([]int,len(nums))dp[0] = nums[0]ans := dp[0]for i := 1;i < len(nums);i++{dp[i] = max(dp[i-1],0) + nums[i]ans = max(ans,dp[i])}return ans}func max(a int,b int)int{if a > b{return a}return b}
62. 不同路径 中等
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
提示：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 109
题解概要：
- 使用动态规划五步分析法。
- 明确dp的含义：dp[i][j]代表到达i,j格子一共有多少种路径。
- 递推公式：由于机器人只能往右和往下移动，那么机器人可以在i-1,j时往下移动一格到达i,j。也可以在i,j-1时往右移动一格到达i,j。因此，dp[i][j] = dp[i-1][j] + dp[i][j-1]。
- 初始值：dp[i][0] = 1 ,dp[0][j] = 1，由于计算的是多少种路径，所以需要初始为1。
- 遍历顺序：先遍历i,再遍历j，双层遍历。
举例：略
代码： ```go func uniquePaths(m int, n int) int {dp := make([][]int,m)
//初始化dp竖排 for i,_ := range dp{
dp[i] = make([]int,n)dp[i][0] = 1
}
//初始化dp横排 for j,_ := range dp[0]{
dp[0][j] = 1
}
for i := 1;i < m;i++{
for j := 1;j < n;j++{dp[i][j] = dp[i-1][j] + dp[i][j-1]}
}
return dp[m-1][n-1]
}
---<a name="XRkMf"></a>#### [63. 不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/) 中等<br />一个机器人位于一个 _m x n _网格的左上角 （起始点在下图中标记为“Start” ）。<br />机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。<br />现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？<br /><br />网格中的障碍物和空位置分别用 1 和 0 来表示。**示例 1：**<br /><br />输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]<br />输出：2<br />解释：<br />3x3 网格的正中间有一个障碍物。<br />从左上角到右下角一共有 2 条不同的路径：<br />1. 向右 -> 向右 -> 向下 -> 向下<br />2. 向下 -> 向下 -> 向右 -> 向右**提示：**<br />m == obstacleGrid.length<br />n == obstacleGrid[i].length<br />1 <= m, n <= 100<br />obstacleGrid[i][j] 为 0 或 1**题解概要：**1. 使用动态规划五步分析法。1. 明确dp的含义：dp[i][j]代表到达i,j格子一共有多少种路径。1. 递推公式：由于机器人只能往右和往下移动，那么机器人可以在i-1,j时往下移动一格到达i,j。也可以在i,j-1时往右移动一格到达i,j。因此，dp[i][j] = dp[i-1][j] + dp[i][j-1]。 **注意：当本格为障碍物时直接跳过即可，因为不可能到达格子。**1. 初始值：dp[i][0] = 1 ,dp[0][j] = 1，由于计算的是多少种路径，所以需要初始为1。**注意：当出现障碍物时后面的路径就为0了，因为不可能到达。**1. 遍历顺序：先遍历i,再遍历j，双层遍历。1. 举例：略<br />**代码：**```gofunc uniquePathsWithObstacles(obstacleGrid [][]int) int {m := len(obstacleGrid)n := len(obstacleGrid[0])dp := make([][]int,m)for i,_ := range dp{dp[i] = make([]int,n)}//初始化竖排for i,_ := range dp{if obstacleGrid[i][0] == 1{break}dp[i][0] = 1}//初始化横排for j,_ := range dp[0]{if obstacleGrid[0][j] == 1{break}dp[0][j] = 1}for i := 1;i < m;i++{for j := 1;j < n;j++{if obstacleGrid[i][j] != 1{dp[i][j] = dp[i-1][j] + dp[i][j-1]}}}return dp[m-1][n-1]}
64. 最小路径和 中等
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
题解概要：
- 使用动态规划五步分析法。
- 明确dp的含义：dp[i][j]代表到达i,j格子路径上数字最小值。。
- 递推公式：由于只能往右和往下移动，那么可以在i-1,j时往下移动一格到达i,j。也可以在i,j-1时往右移动一格到达i,j。因此，dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
- 初始值：dp[i][0] 与dp[0][j]都为 路径上值的和。
- 遍历顺序：先遍历i,再遍历j，双层遍历。
举例：略
代码： ```go func minPathSum(grid [][]int) int {m := len(grid) n := len(grid[0])
dp := make([][]int,m)
for i,_ := range dp{
dp[i] = make([]int,n)
}
sm := 0 for i := 0;i < m;i++{
sm += grid[i][0]dp[i][0] = sm
}
sn := 0 for j := 0;j < n;j++{
sn += grid[0][j]dp[0][j] = sn
}
for i := 1;i < m;i++{
for j := 1;j < n;j++{dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]}
}
return dp[m-1][n-1]
}
func min(a int,b int)int{ if a < b{ return a } return b }
---<a name="N3ld6"></a>#### [343. 整数拆分](https://leetcode-cn.com/problems/integer-break/) 中等给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。<br />返回 你可以获得的最大乘积 。**示例 1:**<br />输入: n = 2<br />输出: 1<br />解释: 2 = 1 + 1, 1 × 1 = 1。**示例 2:**<br />输入: n = 10<br />输出: 36<br />解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。<br /> <br />**提示:**<br />2 <= n <= 58**题解概要：**1. 使用动态规划五步分析法。1. 明确dp的含义：dp[i]代表分解整数i可以获得最大乘积。1. 递推公式：dp[i] = max(dp[i-j],i-j)*j。两者取最大的。1. 初始值：由于n不小于2，则dp[1] = 0 dp[2] = 1,直接初始化即可1. 遍历顺序：先遍历i,再遍历j。i从3开始，j从1开始。顺序遍历1. 举例：dp[3] = 1 * 2= 2dp[4] = 2*2 = 4<br /> <br />**代码：**```gofunc integerBreak(n int) int {dp := make([]int,n+1)dp[2] = 1for i := 3;i <= n;i++{for j := 1;j < i;j ++{dp[i] = max(max(dp[i-j],i-j)*j,dp[i])}}return dp[n]}func max(a int,b int)int{if a > b{return a}return b}
96. 不同的二叉搜索树 中等
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
题解概要：
func numTrees(n int) int {dp := make([]int,n+1)dp[0] = 1for i := 1;i <= n;i++{for j := 1;j <= i;j++{dp[i] += dp[j - 1] * dp[i - j];}}return dp[n]}
1262. 可被三整除的最大和 中等
给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
示例 1：
输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
示例 2：
输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。
示例 3：
输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。
提示：
- 1 <= nums.length <= 4 * 10^4
- 1 <= nums[i] <= 10^4
题解概要：
1.每一步都有3种状态：被3整除、余1和余2。
2.让i右移一位是方便初始化。
3.dp[0][1]与dp[0][2]需要初始化为一个足够小的值。这样才不需要写额外的判断。因为，出现过余1和余2的情况才可以更新dp[0][1]和dp[0][2]的值。
代码：
func maxSumDivThree(nums []int) int {n := len(nums)dp := make([][3]int,n+1)dp[0][1] = math.MinInt32dp[0][2] = math.MinInt32for i := 1;i <= n;i++{num := nums[i-1]%3if num == 0{dp[i][0] = max(dp[i-1][0],dp[i-1][0]+nums[i-1])dp[i][1] = max(dp[i-1][1],dp[i-1][1]+nums[i-1])dp[i][2] = max(dp[i-1][2],dp[i-1][2]+nums[i-1])}else if num == 1{dp[i][0] = max(dp[i-1][0],dp[i-1][2]+nums[i-1])dp[i][1] = max(dp[i-1][1],dp[i-1][0]+nums[i-1])dp[i][2] = max(dp[i-1][2],dp[i-1][1]+nums[i-1])}else{dp[i][0] = max(dp[i-1][0],dp[i-1][1]+nums[i-1])dp[i][1] = max(dp[i-1][1],dp[i-1][2]+nums[i-1])dp[i][2] = max(dp[i-1][2],dp[i-1][0]+nums[i-1])}}return dp[n][0]}func max(a,b int)int{if a > b{return a}return b}
152. 乘积最大子数组 中等
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
- 1 <= nums.length <= 2 * 104
- -10 <= nums[i] <= 10
- nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
题解概要：
1.这道题和最大和不同的是相乘时会改变符号。若一个数组中最大的数乘以负数则乘积就为最小，最小的数乘以负数乘积就为最大。因此，我们要同时记录以nums[i]结尾的最大乘积和最小乘积。若遇到nums[i]是负数时，则对换最大乘积和最小乘积，然后再得到以nums[i]结尾的最大乘积和最小乘积。
代码：
func maxProduct(nums []int) int {n := len(nums)if n == 1{return nums[0]}iMin := nums[0]iMax := nums[0]ans := nums[0]for i := 1;i < n;i++{if nums[i] < 0{ //nums[i]<0需要交换最大乘积和最小乘积tmp := iMiniMin = iMaxiMax = tmp}iMax = max(iMax*nums[i],nums[i]) //求以nums[i]结尾的最大乘积iMin = min(iMin*nums[i],nums[i]) //求以nums[i]结尾的最小乘积ans = max(iMax,ans)}return ans}func max(a,b int)int{if a > b{return a}return b}func min(a,b int)int{if a < b{return a}return b}
4. 背包问题必须 掌握
背包问题的推导可以参考代码狂想录的讲解，非常的清晰。
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html#_01-%E8%83%8C%E5%8C%85
01背包二维推导公式：
//i代表物品，j代表背包重量dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])//双层遍历，先遍历物品后遍历背包。for i := 1; i < len(nums);i++{for j := weight[i];j <= target;j++{dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])}}
01背包一维推导公式：
//j代表背包重量dp[j] = max(dp[j],dp[j-weight[i]]+values[i])//双层遍历，先遍历物品后遍历背包。顺序一定不能颠倒。并且遍历背包时需要倒序遍历！for i := 1; i < len(nums);i++{for j := target;j>= weight[i];j--{dp[j] = max(dp[j],dp[j-weight[i]]+values[i])}}
01背包求组合数：
//j代表组合数dp[j] = dp[j] + dp[j-nums[i]]dp[0] = 1//双层遍历，先遍历物品后遍历背包。顺序一定不能颠倒。并且遍历背包时需要倒序遍历！for i := 1; i < len(nums);i++{for j := target;j>= weight[i];j--{dp[j] = dp[j] + dp[j-nums[i]]}}
完全背包求组合数：
//j代表组合数dp[j] = dp[j] + dp[j-nums[i]]dp[0] = 1//双层遍历，先遍历物品后遍历背包。顺序一定不能颠倒。一定要正序遍历。for i := 1; i < len(nums);i++{for j := nums[i];j<=target;j++{dp[j] = dp[j] + dp[j-nums[i]]}}
完全背包求排列数：
//j代表排列数dp[j] = dp[j] + dp[j-nums[i]]dp[0] = 1//双层遍历，先遍历背包后遍历物品。顺序一定不能颠倒。一定要正序遍历。for (int j = 0; j <= target; j++) { // 遍历背包容量for (int i = 0; i < len(nums); i++) { // 遍历物品if (j - nums[i] >= 0) dp[j] += dp[j - nums[i]];}}
完全背包去装满：
416. 分割等和子集 中等
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
题解概要：
func canPartition(nums []int) bool {n := len(nums)if n <= 1{return false}sum := 0for _,v := range nums{sum += v}target := sum/2if sum % 2 == 1{return false}dp := make([]int,target+1)for i := 0;i < n;i++{for j := target;j >= nums[i];j--{dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])//由于是滚动数组，找到后就返回,终止递归。if dp[j] == target{return true}}}return false}func max(a,b int)int{if a > b{return a}return b}
1049. 最后一块石头的重量 II 中等
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
提示：
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 100
题解概要：
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
func lastStoneWeightII(stones []int) int {n := len(stones)if n == 1{return stones[0]}sum := 0for _,v := range stones{sum += v}target := sum / 2dp := make([]int,target+1)for i := 0;i < n;i++{for j := target;j >= stones[i];j--{dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])}}return sum-dp[target]*2}func max(a int,b int)int{if a > b{return a}return b}
494. 目标和 中等
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
题解概要：
1.假设我们令 相加部分的和为x，那么相减部分的和就为sum-x。那么一定有 x-(sum-x) = target,即 x = (target+sum) / 2。这就转换为01背包问题。
2.边界条件，当target的绝对值大于sum 时，此时一定不可能。当 target+sum 不为偶数时，也不可能求解。
3.由于本题求的是组合问题，那么dp[0] = 1，代表装满背包0一共有1种方法。
4.且dp[j] = dp[j] + dp[j-nums[i]],求的是方法数，因此要叠加。
代码：
func findTargetSumWays(nums []int, target int) int {sum := 0for _,v := range nums{sum += v}if (sum+target) % 2 == 1 || abs(target) > abs(sum){return 0}bagSize := (sum+target)/2dp := make([]int,bagSize+1)dp[0] = 1for i := 0;i < len(nums);i++{for j := bagSize;j >= nums[i];j--{dp[j] += dp[j-nums[i]]}}return dp[bagSize]}func abs(a int)int{if a < 0{return -a}return a}
518. 零钱兑换 II 中等
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
题解概要：
完全背包问题，解题如下
https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html#%E6%80%9D%E8%B7%AF
代码：
func change(amount int, coins []int) int {dp := make([]int,amount+1)dp[0] = 1for i := 0;i < len(coins);i++{for j := coins[i];j <= amount;j++{dp[j] += dp[j-coins[i]]}}return dp[amount]}
322. 零钱兑换 中等
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
题解概要：
1.本题是完全背包问题。
2.dp[i]的定义代表组成i金额的最少硬币数。
3.dp[j] = min(dp[j],dp[j-nums[i]] + 1) //在j-nums金额时，再选择i这枚硬币,因此硬币数要加1。再与dp[j]进行比较。
4.遍历顺序先物品再背包，顺序遍历。
5.由于本题是求最小值，因此除了dp[0]外，其余值都需要初始化为最大值。
代码：
import "math"func coinChange(coins []int, amount int) int {//硬币的最少个数dp := make([]int,amount+1)for i,_ := range dp{dp[i] = math.MaxInt32}dp[0] = 0 //初始化值for i := 0;i < len(coins);i++{for j := coins[i];j <= amount;j++{if j-coins[i] != math.MaxInt32{dp[j] = min(dp[j],dp[j-coins[i]]+1)}}}//因为求最小值，所以初始化为最大值，不然值会被覆盖。if dp[amount] == math.MaxInt32{return -1}return dp[amount]}func min(a int,b int)int{if a > b{return b}return a}
377. 组合总和 Ⅳ 中等
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
题解概要：
1.本题是完全背包问题求排列数，套用模板即可。
2.求排列数先遍历背包再遍历物品，求组合数先遍历物品后遍历背包。
代码：
func combinationSum4(nums []int, target int) int {dp := make([]int,target+1)dp[0] = 1//遍历背包for j := 0;j <= target;j++{for i := 0;i < len(nums);i++{if j >= nums[i]{dp[j] += dp[j-nums[i]]}}}return dp[target]}
279. 完全平方数 中等
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
题解概要：
1.本题是完全背包问题求最小数量问题。
代码：
import "math"func numSquares(n int) int {dp := make([]int,n+1)//初始化最大值for i := 1;i <= n;i++{dp[i] = math.MaxInt32}for i := 0; i <= n;i++{for j := i*i;j <= n;j++{if dp[j-i*i] != math.MaxInt32{dp[j] = min(dp[j-i*i]+1,dp[j])}}}return dp[n]}func min(a int,b int)int{if a < b{return a}return b}
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 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
题解概要：
- 使用动态规划五步分析法。
- 明确dp的含义：dp[i]代表偷窃i个屋子可以偷到的最高金额。
- 递推公式：dp[i] = max(dp[i-2]+nums[i],dp[i-1])。某一个屋子只有偷与不偷两种状态。若当前屋子不偷，则dp[i] = dp[i-1]；若当前屋子偷了,则前一间屋子没偷。dp[i] = dp[i-2] + nums[i]。
- 初始值：dp[0] = nums[0],dp[1] = max(nums[0],nums[1])
- 遍历顺序：顺序遍历
举例：略
代码： ```go func rob(nums []int) int {if len(nums) == 1{
return nums[0]
}
dp := make([]int,len(nums))
dp[0] = nums[0] dp[1] = max(nums[0],nums[1])
for i := 2;i < len(nums);i++{
dp[i] = max(dp[i-2]+nums[i],dp[i-1])
}
return dp[len(nums)-1] }
func max(a int,b int)int{
if a > b{return a}return b
}
---<a name="OKdEF"></a>#### [213. 打家劫舍 II](https://leetcode-cn.com/problems/house-robber-ii/) 中等你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。**示例 1：**<br />输入：nums = [2,3,2]<br />输出：3<br />解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。**示例 2：**<br />输入：nums = [1,2,3,1]<br />输出：4<br />解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。<br /> 偷窃到的最高金额 = 1 + 3 = 4 。**示例 3：**<br />输入：nums = [1,2,3]<br />输出：3**提示：**- 1 <= nums.length <= 100- 0 <= nums[i] <= 1000**题解概要：**[https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html#_213-%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8Dii](https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html#_213-%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8Dii)<br /> <br />**代码：**```gofunc rob(nums []int) int {n := len(nums)if n == 1{return nums[0]}return max(robAmount(nums[1:]),robAmount(nums[:len(nums)-1]))}func robAmount(nums []int)int{n := len(nums)if n == 1{return nums[0]}dp := make([]int,len(nums))dp[0] = nums[0]dp[1] = max(nums[0],nums[1])for i := 2;i < len(nums);i++{dp[i] = max(dp[i-2]+nums[i],dp[i-1])}return dp[n-1]}func max(a int,b int)int{if a > b{return a}return b}
337. 打家劫舍 III 中等
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
- 树的节点数在 [1, 104] 范围内
- 0 <= Node.val <= 104
题解概要：
https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html#%E6%80%9D%E8%B7%AF
每个节点都有两种选择，偷或不偷。用后序遍历保存状态。
代码：
func rob(root *TreeNode) int {ans := robNum(root)return max(ans[0],ans[1])}func robNum(node *TreeNode)[]int{if node == nil{return []int{0,0}}//后序遍历left := robNum(node.Left)right := robNum(node.Right)//如果偷当前房子robCur := node.Val + left[1] + right[1] //左右子树都不可以偷noRobCur := max(left[0],left[1]) + max(right[0],right[1])return []int{robCur,noRobCur}}func max(a int,b int)int{if a > b{return a}return b}
6. 股票问题必须 掌握
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。
提示：
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
题解概要：
本题只能买卖一次。
- 使用动态规划五步分析法。
- 明确dp的含义：dp[i][0]代表第i天持有股票可拥有的最大现金，dp[i][1]代表第i天不持有股票可拥有的最大现金。
递推公式：dp[i][0] = max(dp[i-1][0],-prices[i])。
持有有两种情况：前一天持有、前一天不持有，今天买入。<br /> dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])<br /> 不持有有两种情况：前一天不持有，前一天持有，今日卖出。
初始值：dp[0][0] = - prices[0],dp[0][1] = 0
- 遍历顺序：顺序遍历
- 举例：略
代码：
func maxProfit(prices []int) int {n := len(prices)dp := make([][2]int,n)dp[0][0] = -prices[0]for i := 1;i < n;i++{dp[i][0] = max(dp[i-1][0],-prices[i])dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])}return dp[n-1][1]}func max(a,b int)int{if a > b{return a}return b}
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 。
示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
- 1 <= prices.length <= 3 * 104
- 0 <= prices[i] <= 104
题解概要：
本题可以买卖多次。
- 使用动态规划五步分析法。
- 明确dp的含义：dp[i][0]代表第i天持有股票可拥有的最大现金，dp[i][1]代表第i天不持有股票可拥有的最大现金。
递推公式：dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])。
持有有两种情况：前一天持有、前一天不持有，今天买入。<br /> dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])<br /> 不持有有两种情况：前一天不持有，前一天持有，今日卖出。
初始值：dp[0][0] = - prices[0],dp[0][1] = 0
- 遍历顺序：顺序遍历
- 举例：略
代码：
func maxProfit(prices []int) int {n := len(prices)dp := make([][2]int,n)dp[0][0] = -prices[0]for i := 1;i < n;i++{dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])}return dp[n-1][1]}func max(a,b int)int{if a > b{return a}return b}
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
提示：
- 1 <= prices.length <= 5 * 104
- 1 <= prices[i] < 5 * 104
- 0 <= fee < 5 * 104
题解概要：
1.这道题和买卖股票最佳时机2思路一致，只是在买入的时候多付一笔税费。
代码：
func maxProfit(prices []int, fee int) int {n := len(prices)dp := make([][2]int,n)dp[0][0] = -prices[0]for i := 1;i < n;i++{dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]-fee) //完成交易时支付一笔税费。}return dp[n-1][1]}func max(a,b int)int{if a > b{return a}return b}
123. 买卖股票的最佳时机 III 困难
给定一个数组，它的第 _i 个元素是一支给定的股票在第 i _天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
提示：
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 105
题解概要：
本题最多可以买卖两次。因此，第一共有5种状态：不操作、第一次买入、第一次卖出、第二次买入、第二次卖出。
递推公式：
dp[i][0] = dp[i-1][0] //不进行操作
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]) //第一次买入
dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]) //第一次卖出
dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i]) //第二次买入
dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i]) //第二次卖出
代码：
func maxProfit(prices []int) int {
n := len(prices)
dp := make([][5]int,n)
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
for i := 1;i < n;i++{
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])
dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i])
dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i])
dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i])
}
return dp[n-1][4]
}
func max(a,b int)int{
if a > b{
return a
}
return b
}
188. 买卖股票的最佳时机 IV 困难
给定一个整数数组 prices ，它的第 _i 个元素 prices[i] 是一支给定的股票在第 i _天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
- 0 <= k <= 100
- 0 <= prices.length <= 1000
- 0 <= prices[i] <= 1000
题解概要：
代码：
func maxProfit(k int, prices []int) int {
n := len(prices)
if n == 0{
return 0
}
dp := make([][]int,n)
for i,_ := range dp{
dp[i] = make([]int,2*k+1)
}
for i:= 1;i<2*k+1;i+=2{
dp[0][i] -= prices[0]
}
for i := 1;i < n;i++{
dp[i][0] = dp[i-1][0]
per := -1 //操作符
for j := 1;j < 2*k+1;j++{
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] + per*prices[i])
per *= -1
}
}
return dp[n-1][2*k]
}
func max(a,b int)int{
if a > b{
return a
}
return b
}
309. 最佳买卖股票时机含冷冻期 中等
给定一个整数数组prices，其中第 _prices[i] 表示第 _i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
题解概要：
共有3种状态：持有股票、不持有股票（在冷冻期内）、不持有股票（不在冷冻期内）。
第i天持有股票：
1.第i-1天持有股票。
2.第i-1天不持有股票且不在冷冻期内，第i天买入股票。
第i天不持有股票(在冷冻期内)：
1.第i-1天持有股票，并且卖出。
第i天不持有股票(不在冷冻期内)
1.第i-1天不持有股票且不在冷冻期内
2.第i-1天不持有股票且在冷冻期内
最后：不持有股票的两种情况取最大值，即为利润的最大值。
递推公式：
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][2], dp[i-1][1])
代码：
func maxProfit(prices []int) int {
n := len(prices)
if n == 0 {
return 0
}
dp := make([][3]int,n)
dp[0][0] = -prices[0]
for i := 1;i < n;i++{
dp[i][0] = max(dp[i-1][0],dp[i-1][2]-prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][2],dp[i-1][1])
}
return max(dp[n-1][1],dp[n-1][2])
}
func max(a,b int)int{
if a > b{
return a
}
return b
}
7. 子序列问题必须 掌握
300. 最长递增子序列 中等
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
- 1 <= nums.length <= 2500
- -104 <= nums[i] <= 104
题解概要：
https://programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html
代码：
func lengthOfLIS(nums []int) int {
n := len(nums)
dp := make([]int,n)
dp[0] = 1
ans := 1
for i := 1;i < n;i++{
dp[i] = 1
for j := 0;j < i;j++{
if nums[i] > nums[j]{
dp[i] = max(dp[i],dp[j]+1)
}
}
ans = max(ans,dp[i])
}
return ans
}
func max(a,b int)int{
if a > b{
return a
}
return b
}
673. 最长递增子序列的个数 中等
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
提示:
- 1 <= nums.length <= 2000
- -106 <= nums[i] <= 106
题解概要：
代码：
func findNumberOfLIS(nums []int) int {
n := len(nums)
if n == 1{
return 1
}
dp := make([]int,n) //代表以nums[i]结尾的最大子序列
count := make([]int,n) //代表以nums[i]结尾最大子序列的个数
dp[0] = 1
count[0] = 1
maxLen := 1 //最大子序列的长度
for i := 1;i < n;i++{
dp[i] = 1
count[i] = 1
for j := 0;j < i;j++{
if nums[i] <= nums[j]{
continue
}
if dp[j] + 1 > dp[i]{
dp[i] = dp[j]+1
count[i] = count[j] //出现了新的最长子序列，则count[i] = count[j]。
//count表示是个数,和方法数类似。
}else if dp[j] + 1 == dp[i]{
count[i] += count[j] //两者相加
}
}
maxLen = max(maxLen,dp[i])
}
//
ans := 0
for i,_ := range dp{
if maxLen == dp[i]{
ans += count[i]
}
}
return ans
}
func max(a,b int)int{
if a > b{
return a
}
return b
}
674. 最长连续递增序列 简单
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
提示：
- 1 <= nums.length <= 104
- -109 <= nums[i] <= 109
题解概要：
1.dp[n]代表以n结尾的最长连续递增子序列的长度。
2.若nums[i] > nums[i-1] 时，dp[i] = dp[i-1] + 1，否则 dp[i] = 1。
代码：
func findLengthOfLCIS(nums []int) int {
n := len(nums)
dp := make([]int,n)
dp[0] = 1
ans := 1
for i := 1;i < n;i++{
if nums[i] > nums[i-1]{
dp[i] = dp[i-1]+1
}else{
dp[i] = 1
}
ans = max(ans,dp[i])
}
return ans
}
func max(a,b int)int{
if a > b{
return a
}
return b
}
718. 最长重复子数组 中等
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
题解概要：
代码：
func findLength(nums1 []int, nums2 []int) int {
n1 := len(nums1)
n2 := len(nums2)
dp := make([][]int,n1+1)
for i,_ := range dp{
dp[i] = make([]int,n2+1)
}
ans := 0
for i := 1;i <= n1;i++{
for j := 1;j <= n2;j++{
//由于求的是连续子数组，因此相等时+1，不相等时不进行赋值
if nums1[i-1] == nums2[j-1]{
dp[i][j] = dp[i-1][j-1] + 1
}
ans = max(ans,dp[i][j])
}
}
return ans
}
func max(a,b int)int{
if a > b{
return a
}
return b
}
1143. 最长公共子序列 中等
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。
示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。
题解概要：
代码：
func longestCommonSubsequence(text1 string, text2 string) int {
n1 := len(text1)
n2 := len(text2)
dp := make([][]int,n1+1)
for i,_ := range dp{
dp[i] = make([]int,n2+1)
}
for i := 1;i <= n1;i++{
for j := 1;j <= n2;j++{
//由于求的是子序列，因此不相等时要看左一位和上一位。
if text1[i-1] == text2[j-1]{
dp[i][j] = dp[i-1][j-1] + 1
}else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
}
}
}
return dp[n1][n2]
}
func max(a,b int)int{
if a > b{
return a
}
return b
}
若有收获，就点个赞吧
0 人点赞
