看看目前为止做过的动态规划题目
算法导论课+Hot100DP
动态规划，是两种思想的结合：分治思想（子问题）+解决冗余(填表查表)；动态规划可解的前提，是原问题具备最优子结构，通过一步操作（转移方程），将原问题转为子问题求解
- 可总结为：最优子结构，重叠子问题
- 同时也是判断一个思路是否符合DP的标准
- 是否具备最优子结构（不重不漏+最优性原理），需要打开思路；常需要列举，max, min 等求解；
- 对于求解问题需要明确，以定义最优值
- 求解当前问题时，是建立在已知全部子问题解的假设下的。原问题应该由子问题不重不漏的组成。
- 做dP过程遇到一些技巧题(变形)
- 1-“股票买卖问题:由于含有冷冻期，定义目标解时，每个状态(第i天)的最大收益，通过max{…}表示，基于此设计状态转移方程
- 2-打家劫舍III。此题最优解的定义与股票买卖问题有异曲同工之妙。同时，是dp和树的结合(想想为什么是后续遍历)
- 3-分割等和子集：对所求目标变形。dp过程的目标解，并非来自直接题目所求，而是需要做一定的换算
- DP的艺术很大一部分来自目标解的定义。
- 上面的变形题，不管是max/min{ }来间接表示目标解，还是通过约束进行计算转换，都是
- 还有，单单是目标解本身定义的好，往往在求解时就能茅舍顿开-见 “最大正方形面积”
sum_Note_20220223:
- 复习一遍
- 做Dp，一定要清楚子问题是什么？如果子问题无法很好入手和得到，那么可不可以将原问题拆解为多个“不重不漏”的问题的集合（比如冷冻期股票问题、最大乘积数组、求最长无重复字符 子字符串长度），最后用max{}等技巧来求解。分解原问题，目的是为了更好的“新的问题”下的“子问题”。只有原问题和子问题清楚，才能使用动态规划，设计 动态转移方程。
切杆问题
%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-72%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5B%22%20x%3D%22451%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6E%22%20x%3D%22730%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5D%22%20x%3D%221330%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%221886%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6D%22%20x%3D%222943%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-61%22%20x%3D%223821%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(4351%2C0)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-78%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(572%2C-150)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(353%2C0)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-3C%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%22778%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-69%22%20x%3D%222057%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(1699%2C0)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-3C%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%22778%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(2800%2C0)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-30%22%20x%3D%22500%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-7B%22%20x%3D%228531%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-72%22%20x%3D%229032%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5B%22%20x%3D%229483%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6E%22%20x%3D%229762%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2212%22%20x%3D%2210584%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-69%22%20x%3D%2211585%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5D%22%20x%3D%2211930%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%2212431%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%2213432%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5B%22%20x%3D%2213935%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-69%22%20x%3D%2214214%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5D%22%20x%3D%2214559%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-7D%22%20x%3D%2214838%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=r%5Bn%5D%3Dmax_%7B1%3C%3Di%3C%3D10%7D%5C%7Br%5Bn-i%5D%2Bp%5Bi%5D%5C%7D%0A&id=R25Q6)
剑指 Offer 14- I. 剪绳子
此题我认为本质也是“切杆问题”
这道题在解的时候，容易陷入剪几段不确定，要列举很多情况的误区。实际上，定义f[m] 为长度为m下，符合题意的最优解。写动态转移方程时，便可以轻松包含全部“剪法的情况”：
剪成任意多段（>2），肯定第一刀是剪成2段, 或者说剪得再碎，也能拼成两段。所以这就是一个常见的dp问题。小细节是,因为至少要剪一刀,注意f[ ]的初始条件和特殊情况下的直接返回值，并不是对应的。
背包问题
边界条件：
dp[i][j] = 0 ; if i=0
dp[i][j] = 0; if j = 0 ;
效率：O（nW）
矩阵链乘问题
此DP难的是对问题的抽象
在实现代码时，可以用自底向上的方式，以链长l 递增方向
扩展思考： 如何优雅的打印链乘结果？
…
最长子序列
求构成数的最小数量平方和
求最長遞增子序列(dp解、dp解2-貪心思想)
dp解1
dp解2-利用贪心思想
这里关键，find 第一个 小于nums[i的的dp 位置pos，更新dp[pos+1]位置
举例：已有子序列 <2>-<4><6>
if num[i] = 5 , pos = 2 , 更新dp[3]=5 , 得 <2><4><5>
if num[i] = 3 , pos = 1 , 更新dp[2]=3 , 得 <2><3><5>
股票买卖含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析：
之前的草稿，虽然字好丑懒得写了，将就看吧🤣
最小硬币数
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
将dp[i]初始化为一个大数{flag+1}，最后return dp[amount] >flage ? -1 : dp[amount] 即可
小偷偷家
- 题目描述
- 小偷偷家，不能偷相邻的两家。传入一个nums数组，值是每一家的财产，均大于零，求最佳的偷家结果
分析-看官方解：
- 这里其实有个细节需要好好推敲，对于dp[i], 确实只有2种情况，nums[i]选还是不选；不选择，则dp[i] = dp[i-1]. 但关键是选择的时候，这里dp[i] = dp[i-2]+nums[i]; 但我们并不知道dp[i-1]是选了nums[i-1]，还是没选nums[i-1]，似乎dp[i-1]要是没选，则最优解应该是dp[i-1]+nums[i], 我们并没有考虑到这个情况; 但实际上，这个动态规划方程恰好囊括了全部情况的最优解，我们再进一步分析：
- 假设dp[i-1]选了nums[i-1]，那么di[i]=max{dp[i-1],dp[i-2]+nums[i]}毫无疑问是对的
- 假设dp[i-1]没选nums[i-1], 则dp[i-1] = dp[i-2], 故di[i]=max{dp[i-1],dp[i-2]+nums[i]} 考虑了所有的情况
分析-另外一种解
- 有时候不一定会想得这么仔细，这里提供另外一种解
- f[i] 表示考虑第1,…,第i家时，第i家选择时的最佳偷窃策略
- g[i] 表示考虑第1,…,第i家时，第i家不选择时的最佳偷窃策略
- 目标解Max{f[i],g[i] }
- 状态转移方程：
- f[i] = g[i-1]+nums[i]
- g[i] = max{g[i-1],f[i-1]}
打家劫舍III
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3<br /> / \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
分析
- 首先本题是dp问题和二叉树的结合。如何结合？根节点的状态作为原问题，将子问题的解(状态)作为子孙节点的状态。对二叉树的后续遍历，由于祖先后遍历，相当于一般动态规划问题自底向上求解的过程。当然，代码写成后续递归遍历(简单)，就是对应动态规划问题自顶向下求解。Anyway实现方式不是重点，重点是，dp思想恰好通过后续遍历进行体现：访问祖先之前，全部孙子均已遍历，求解原问题时，子问题全部解已知。
- 第二个要点，类似于股票求解问题。用 max{ }结构定义最优解，这样写状态转移方程时，更简单。
解：
能否分割等和子集
分析：
- 这是一个NP问题，所以我们的思路是，能否分割等和子集，并没有多项式时间内能求解的方法
- 先求数组全部元素和sum。 数组长度小于2，不可；sum 是奇数，不可；sum是偶数，dp_target = sum/2 ， 转化为背包问题求解
- 这样做有什么好处?只管只要能够挑选一些元素，使其和等于dp_target, 就求解了原问题：能否分割等和子集
优化空间复杂度:滚动数组
- 注意到每个问题的状态:dp[i][j]只由两个子问题的状态决定
- dp[i-1][j-nums[i]] —>dp[j-nums[i]]
- dp[i-1][j] —> dp[j]
- 所以最少只需要用一个一纬数组保存此刻状态，并不断更新即可：
- when i=i, dp[j] = dp[j] || dp[j-nums[i]]
- 外层循环是i-从小到大 , 内层循环是j-必须从大到小，因为需要用到旧值，j>j-nums,故dp[j]要先更新
寻找目标和(本题和上一题是一类)
分析
- 基本思路就是转换为背包问题
能否从Nums[ ]中挑选一些数，使其和为newTar=(sum+tar)/2
分析
- 必须掌握的是 中心 拓展算法（非DP）
class Solution {public int countSubstrings(String s){int l = s.length();int cou=0;for(int i=0;i<2*l-1;i++){//枚举每个中心（每个中心点的left,right坐标）int left = i/2;int right = i/2+i%2;while(left>=0 && right<l && s.charAt(left)==s.charAt(right)){cou++;left--;right++;}}return cou;}}
- 动态规划算法
- 看下题，对dp[][]数组，统计值为true的个数，即为本题的解
- Manacher 算法-DP
- 埋个坑，后面再补吧..
最长回文串
分析
- 本题和上一题本质是同一道题，解题方法是互通的。
- 因为无论是求解回文子串的数量还是 求解最长回文子串，都需要遍历所有是回文子串的状态
- 下面给出DP求解方法（非马拉车算法）
注意实现时，枚举的是子字符串的长度 ```java public String longestPalindrome(String s) {
int len = s.length();if(len<2) return s;char[] sChar = s.toCharArray();boolean dp[][] = new boolean[len][len];//初始化,另外一个边界条件不需要刻意初始化for(int i=0;i<len;i++) dp[i][i]=true;int maxLen = 1,beginFlag=0;for(int sublen=2;sublen<=len;sublen++){//从2开始循环，1已求解//枚举所有左端点for(int left=0;left<len;left++){//左端点的上限可以宽松//左端点确定，长度确定，确定右端点int right = left+sublen-1; //记得减一if(right >=len) break;if(sChar[right] != sChar[left]) dp[left][right]=false;else{if(right-left<3){dp[left][right] = true;}else{dp[left][right] = dp[left+1][right-1];}
}if(dp[left][right] && right-left+1 > maxLen){maxLen = right-left+1;beginFlag = left;}}}return s.substring(beginFlag,beginFlag+maxLen);}
<a name="HQUHt"></a>### 最大子序和[53. 最大子数组和](https://leetcode-cn.com/problems/maximum-subarray/)<br /><br />分析：<br /><a name="pPs30"></a>### *最大乘积数组[152. 乘积最大子数组](https://leetcode-cn.com/problems/maximum-product-subarray/)<br />给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积分析- 此题和上一题【最大子序和】有相似的最优解结构，但又不同。因为它的状态转移方程更加复杂。- 由于nums[i]是负数时，负负得正，那么nums[i]<0时，我们需要乘上- 这启发我们，为了写出动态方程，我们不仅需要维护f_max, 还要维护f_min ； **这是很常用的一个技巧**- <a name="zWhNo"></a>### 不同路径I 和 不同路径II- 比较简单就不写了- [63. 不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/)- [62. 不同路径](https://leetcode-cn.com/problems/unique-paths/)<a name="Tt2qb"></a>### *单词拆分
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
分析：- 字符串s能被分解，一定是开头的子串也能被分解。可以抓住这一点，来列举所有可能的情况：- 对于一个字符串s(0,i)，能被分解的情况是存在 j , 使得 s(0 , j) 和s(j, i ) 能被分解；0<i<len- dp[i]表示，s(0,i)是否可以被空格拆分为一个或多个在字典中出现的单词- - 边界条件：dp[0]=true<a name="GilCx"></a>### [140. 单词拆分 I](https://leetcode-cn.com/problems/word-break-ii/)[I](https://leetcode-cn.com/problems/word-break-ii/)字典树<a name="JFwQV"></a>### 求最大正方形面积<br />分析<br /><a name="TaolJ"></a>### 求最长无重复字符子字符串长度请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。注：此题字符串中的字符没有说就是小写字母<br />```javapackage SwordOf.dynamicPro;import org.junit.Test;import java.util.HashMap;import java.util.HashSet;public class LengthOfLongestSubstring {/*剑指上s的值只是小写字母，但leetcode则没有这一限制；所以不能用一个小数组来记录下标了，需要用HashMap<字符，上一次出现的值>*/public int lengthOfLongestSubstring(String s) {if (s.length() == 0) return 0;/* int[] preAppearPosition = new int[26];for (int i = 0; i < 26; i++) {preAppearPosition[i] = -1;}*/HashMap<Character, Integer> map = new HashMap<>();int maxLen = Integer.MIN_VALUE;int len = 0;//len表示当前字符到到上一次该字符出现的情况；len>=1, 1就是相邻aa的情况;int fPre = 0;for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);//该字符从未出现过if (!map.containsKey(ch)) {// fPre = fPre++;fPre++;map.put(ch, i);} else { //该字符出现过//先求两个该字符间的距离，再分两种情况处理len = i - map.get(ch);map.put(ch,i);if (len <= fPre) fPre = len;else {//fPre = fPre++;什么玩意fPre++;}}if (fPre > maxLen) maxLen = fPre;}return maxLen;}@Testpublic void test() {String s = "abcabcbb";int len = lengthOfLongestSubstring(s);System.out.println(len);}@Testpublic void test2() {int i = 0;for (int j = 0; j < 2; j++) {i=++i;// i=i++;}System.out.println(i);}}
若有收获，就点个赞吧
0 人点赞
