🌸 动态规划

🌼 思想

动态规划的本质是把当前问题拆解成若干个子问题，通过求解子问题的最优解，来求解当前问题的最优解。 所以首先要找到当前问题的最优解是什么意义，然后找到子问题，然后找到状态转移方程，也叫递推公式， 即怎么通过子问题的最优解来求解当前问题的最优解。

🪜 解题步骤：

1. 确定dp数组及其下表的含义。
2. 明确结果分类，确定递推公式。
3. 初始化dp数组。
4. 确定遍历顺序。
5. 举例推导dp数组。
6. 确定返回值。

🏀 常见模型： 背包模型有很多变种：01背包、完全背包、多重背包、分组背包等。这里只讲01背包和完全背包。

01背包：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

解题方法：

第一种方法是二维dp数组。

1. dp[i][j]：从下标[0,i]的物品中随便取，放入容量为j的背包中，物品的最大价值是多少。
2. 递推公式：有两种情况，取其中计算出的dp[i][j]最大值。第一种情况是：不把下标为i的物品放入背包中，此时dp[i[j]=dp[i-1][j]。第二种情况是把下标为i的物品放入背包中，此时需要预留出j-weight[i]的容量，子问题就是从下标[0,i-1]的物品中取，背包容量为j-weight[i]，物品的最大价值是多少，即dp[i-1][j-weight[i]]。第二种情况dp[i][j]=value[i]+dp[i-1][j-weight[i]]，当然这里要考虑j-weight[i]<0的情况。最终的递推公式为dp[i][j] = max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]])。
3. 初始化：只需要初始化dp[i][0]和dp[0][j]即可，因为dp[i][j]总是由其上方和左上方的位置推导出来。dp[i][0]可以完全初始化为0，因为背包为0的话，什么也装不了。dp[0][j]初始化时，则需要判断j和weight[0]的大小。
4. 遍历方向：可以从物品编号从小到大开始遍历。也可以从背包容量从小到大遍历。
5. 推导过程：每次确定dp[i][j]时直接打印出来。
6. 结果：dp[n-1][m]

第二种方法是一维dp数组。

1. dp[j]：容量为j的背包，物品的最大价值为dp[j]。
2. 递推公式：遍历[0,i]物品，dp[j] = max(dp[j],dp[j-weight[i]]+value[i])。
3. 初始化：dp[j]只依赖它前面的位置。因此只用初始化dp[0]=0即可。
4. 遍历方向：对于背包容量，是从大到小遍历，为了防止重复取到某个物品。对于物品，从小到大和从大到小没有区别。整个结构是对物品的循环里面嵌套对背包容量的循环，每次循环一个物品i得到的dp数组，代表[0,i]能放入时，背包中物品的最大价值。
5. 推导过程：每次确定dp[i]时打印出来。
6. 结果：dp[m]

完全背包：有n种物品和一个容量为w的背包，每种物品有无限件可用。第i种物品的重量是weight[i]，价值是value[i]。求解将哪些物品装入背包里物品价值总和最大。

二维数组的方法：

1. dp[i][j]：从下标[1-i]的物品中随便取，装入容量为j的背包中，物品价值最大为dp[i]。
2. 递推公式：对于dp[i][j]有两种情况。第一种情况是，不放入下标为i的物品，一个都不放，那dp[i][j]=dp[i-1][j]。第二种情况是，一定会放入下标为i的物品，那么dp[i][j]=dp[i][j-weight[i]]+value[i]。所以最终dp[i][j] = max(dp[i-1][j],dp[i][j-weight[i]]+value[i])
3. 初始化：dp[i][j]依赖于dp[i-1][j]和dp[i][j-weight[i]]，分别在左边和上面，应该先初始化第一列和第一行。其他的位置默认为0。
4. 遍历方向：遍历物品，循环中遍历背包容量。背包容量应该从小到大遍历。
5. 结果：dp[n][w]

一维数组的方法：

1. dp[j]：背包容量为j的背包中，物品价值最大为dp[j]。
2. 递推公式：dp[j] = max(dp[j], dp[j-wight[i]]+value[i])。
3. 初始化：dp[j]只是依赖于dp[j-weight[j]]，初始化所有的dp数组值为0即可。
4. 遍历方向。遍历物品，循环中遍历背包容量，背包容量应该是从小到大遍历。
5. 结果：dp[w]

📓 题目和解析

• 整数拆分

给一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。 返回可以获得的最大乘积。

1. dp[i]：数字i拆分成k个正整数之后的最大乘积，dp[0]和dp[1]不处理，数组长度为n+1。
2. 递推公式：dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))，j的范围是[1,i-1]，目的是通过遍历把i拆分成两个数。
3. 初始化只能初始化到dp[2]，这里虽然dp[1]没有意义，但是我们把它初始化为1会好处理一些。
4. 遍历自然是从前往后遍历。
5. 举例推导，可以把遍历时的打印出来。
6. 输出dp数组最后的一个元素。

这里比较容易搞错递推公式。我们考虑dp[i]应该是在这四个值中取最大值：j*(i-j),jdp[i-j]),(i-j)dp[j],dp[j]dp[i-j]。 在遍历的过程当中，明显j取[1,i-1]的时候，jdp[i-j])和(i-j)dp[j]会被重复的取到。另外考虑dp[j] = ab, a<b的情况，dp[i]dp[i-j]=abdp[i-j]，也可以写成j’ * dp[i-j’] 的形式。所以递推公式应该是dp[i] = max(dp[i],max(j(i-j),j*dp[i-j]))。

• 二叉搜索树的种类

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

1. dp[i]表示恰有i个节点组成的二叉搜索树种类为dp[i]种。
2. 递推公式。对于i，可以把这些搜索二叉树分别分为以1、2、3…i为根节点的二叉搜索树。其中以j为根节点的二叉搜索树，其左子树是一个有j-1个节点的搜索二叉树。右子树是一个有i-j个节点的二叉搜索树，则这一类情况数就为dp[j-1]+dp[i-j]。
3. 初始化dp[1]=1，dp[0]=0即可，i=0的情况相当于空树，是一种情况。
4. 从少到多遍历i，循环内部在从少到多遍历j。i范围为[2,n],j范围为[1,i]。
5. 遍历时打印dp[i]检查即可。
6. 输出dp[n]，数组长度为n+1。

• 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1. dp[i]表示包括nums[i]和它左边的所有房屋的所有情况下，一夜能够偷窃到的最高金额。
2. 递推公式：dp[i] = max(dp[i-1],dp[i-2]+nums[i])。计算dp[i]是分为两种情况，一是访问 nums[1]，而是不访问。第一种情况就不能访问nums[i-1]，所以要访问dp[i-2]。第二种情况很简单， 不访问nums[1]的话，就相当于求dp[i-1]。
3. 初始化，初始化dp[0]=nums[0]，dp[1]=max(nums[0],nums[1])即可。
4. 遍历顺序是从小到大。
5. 在遍历的时候打印dp[i]即可查看推导过程。
6. 返回值是dp的最后一个元素，因此dp数组应该初始化为nums的长度。

• 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

1. dp[i]表示和为i的完全平方数的最少数量。
2. 递推公式：如果i是完全平方数的话，dp[i]=1;如果i不是完全平方数的话，遍历[i/2,i-1]， dp[i] = min(dp[j]+dp[i-j],dp[i])
3. 初始化dp[1]=1，dp[2]=2即可。这里实际应该把dp[i]初始化为i，递推公式取的是min，另外最坏情况就是i个1相加。
4. 从小到大的顺利开始遍历。
5. 在dp[i]取得最终值的地方，打印dp[i]，即可打印出推导公式。
6. 输出dp[n]，对应dp数组长度应该为n+1，为了方便表示dp[0]没有使用。

• 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。

1. dp[i]为能凑齐总金额amount=i的最少的硬币个数。
2. 递推公式：第一种情况是有总金额面额的硬币，则dp[i]=1。第二种情况是只能把i拆成两份j和j-1，dp[i] = min(dp[i],dp[j]+dp[i-j])。但是要保证dp[j]和dp[i-j]都能取得到。j取值是[i/2,i-1]
3. 初始化dp[1]即可，注意要根据coins来初始化。另外i>=2时，dp[i]初始化为i+1。
4. 从小到大遍历。
5. 得到dp[i]时打印即可输出推导结果。
6. 最终输出的应该是dp[amount],dp数组长度应该为amount+1。

上面这个递推公式出问题了，默认了i可以被拆成两份，然后取最后的结果，不过不行的话就得返回-1。但是实际上可能i不会被拆成两份，而是三份甚至更多。 例如coins={2，5}，而amount=6，那么6就不能被拆成两份，而是3份2。

这题目正确的解法应该是

1. dp[i]为能凑齐总金额amount=i的最少的硬币个数。
2. 递推公式：dp[i] = min(dp[i],dp[i-coin]+1)，coin是coins数组中的元素。
3. 初始化dp[0]=0，dp[i]=i+1即可。
4. 从小到大遍历。
5. 得到dp[i]时打印即可输出推导结果。
6. 最终输出的应该是dp[amount],dp数组长度应该为amount+1。

• 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1. dp[i]:s的前缀子串中，长度为i的那个子串能不能被拆分。
2. 递推公式：对于(j,i]部分如果能被字典表示，且dp[j]==true，则dp[i]==true。
3. 初始化：为了让第一个元素能够匹配上，dp[0]==true，其他的dp元素初始化为false。
4. 从小到大遍历
5. 输出dp[len(s)]即可。

• 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32位 整数。

1. dpmax[i]表示以第i个位置结尾的子数组，对应的最大乘积。而dpmin[i]表示以第i个位置结尾的子数组，对应的最小乘积，因为可能有负数。
2. 递推公式：dpmax[i] = max(nums[i],dpmax[i-1]*nums[i],dpmin[i-1]*nums[i])，dpmin[i] = min(nums[i],dpmax[i-1]*nums[i],dpmin[i-1]*nums[i])。
3. 初始化，可以看到每一项只依赖其前一项。所以我们只需要初始化dpmax[0] = nums[0]，dpmin[0] = nums[0]即可。s
4. 从小到大遍历即可。
5. 每次确定dpmax[i]和dpmin[i]时都打印出i和dp[i]可以得到推导过程。
6. 使用一个值来保存最大乘积，最终返回它。
7. 优化，实际上只需要保存前一项的dpmax和dpmin即可进行下一步的推导。不需要一整个数组。

• 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1. dp[i]：包含索引为i的，且以索引i元素结尾的，最长严格递增子序列长度。
2. 递推公式：遍历[1,i-1],如果nums[i]>nums[j]，则dp[i] = max(dp[i],dp[j]+1)。
3. 初始化：所有的都应该初始化为1，至少有当前元素。
4. 从小到大遍历。
5. 记录遇到的最长严格递增子序列长度。最后输出即可。

• 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

1. 物品索引0-i，物品价值nums[i]，物品重量nums[i]，背包容量sum/2，求最大价值，判断是否有sum/2的。
2. dp[j]:背包容量为j，能装物品的最大价值。
3. 递推公式：遍历物品索引，dp[j] = max(dp[j],dp[j-weight[i]]+value[i])。
4. 初始化： 初始所有的元素为0即可。
5. 遍历顺序，从小到大遍历物品索引，循环中从大到小遍历背包容量。
6. 推导过程：每次确定dp[j]都先打印出来。
7. 结果：每确定一次i,j对应的最大价值，查看有没有sum/2的物品价值。

• 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？

1. dp[i][j]：到（i，j）位置总共有dp[i][j]条不同路径。
2. 递推公式：dp[i][j] = dp[i-1][j]+dp[i][j]。
3. 初始化：初始化第一列和第一行为0。
4. 遍历方向：从第i=1行开始遍历每一行，从j=1列开始遍历每一列，从小到大遍历。
5. 结果dp[m-1][n-1]

优化方法：可以优化

1. dp[j]：表示到这行的第j列共有dp[j]条不同的路径。
2. 递推公式：dp[j] = dp[j]+dp[j-1]。
3. 初始化：初始化dp[0]=0即可。
4. 遍历方向：遍历每一行，从小到大开始遍历。循环内从小到大遍历每一列。
5. 结果：dp[n-1]

• 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 **说明：**每次只能向下或者向右移动一步。

1. dp[i][j]：到第i行第j列路径数字总和最小。
2. 递推公式：dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grip[i][j]。注意这个路径和是包含终点的权重的。
3. 初始化：需要初始化第一行和第一列。
4. 遍历方向：从小到大遍历每一行，然后循环内部遍历每一列。
5. 结果：dp[len(grid)-1][len(grid[0]-1)]。