343. 整数拆分  dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。 递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); 要么拆两个直接乘，要么拆两个及以上。 初始化：dp[2] = 1,注意拆0和1没意义。 遍历顺序，从前往后，先得到小的dp再算大的dp。 动态规划里经常考虑实际意义数组下标从1开始才有意义，最后求的也是dp[m],所以数组大小要多开一位。  class Solution { public: int integerBreak(int n) { vector<int> dp(n + 1, 0)...

62.不同路径   dp[i][j]是从（0, 0）出发走到(i, j)的不同路径数.   限定了只能向右或者向下走，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，初始化边界的路径数都为1，遍历顺序从左上到右下每层遍历。   注意小trick，结果是dp[m - 1][n - 1]。自己想的，棒，dp找递推可以先逆着想。   //C++ class Solution { public: int uniquePaths(int m, int n) { //vector<vector<int>> dp(m, vector<int>...

理论基础 动态规划五步骤：  确定dp数组（dp table）以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组验证  509. 斐波那契数 按五步走，dp数组为第i个数的斐波那契数值是dp[i]，地推公式和初始化已给，顺序遍历。 //C++ class Solution { public: int fib(int n) { int dp[31]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } };  ...

738.单调递增的数字 想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。注意实际上是之后的都要为9 想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。 //C++ 自己模拟的，有点笨，可以直接int转string，用flag标记索引为9的位置，避免重复更新9 class Solution { public: int monotoneIncreasingDigits(int n) { vect...

435. 无重叠区间 和打气球类似，根据左边界排序，找重叠就跳结果+1，更新最小右边界。需要注意的是，左边界排序再对右边界排序不能取代更新最小右边界，因为存在左边界更大，右边界也更小也是要更新的。  class Solution { public: static bool cmp(vector<int>& a, vector<int>& b) { if (a[0] == b[0]) return a[1] < b[1]; return a[0] < b[0]; } int eraseOverlapIntervals(vector<vec...

860.柠檬水找零 分三种情况，5就收，10找一张5,20优先找1张10一张5（贪心），再考虑三张5. class Solution { public: bool lemonadeChange(vector<int>& bills) { int five = 0, ten = 0; for (int i = 0; i < bills.size(); i++) { if (bills[i] == 5) five++; if (bills[i] == 10) { five--; ten++; } if (bills[i] == 20) { if (ten > 0) ...

1005.K次取反后最大化的数组和  用两次贪心，第一次先把负数都转过来，第二次如果k还有剩的为奇数再把最小的正数转过来。 注意负数转过来后可能会产生更小的正数，所以一开始排序要不然按绝对值排序，要不然转过来之后再排序一次。 注意一点，选当前点前面的起始点相当于多了油量，二刷借此想法看看第一种全局的方法：1.走一圈剩余油和<0不可能完成2.从0开始走一圈大于0输出，小于0则往前倒退看谁能补齐差的油。  //C++ 两次从小到大排序 class Solution { public: int largestSumAfterKNegations(vector<int>& n...

122.买卖股票的最佳时机II 将整体利润拆分为每天的利润（两天为一个单位），然后只收集正利润。注意不是最长递增序列，可以跳着卖，只要在正利润区间卖出即可。 class Solution { public: int maxProfit(vector<int>& prices) { int result = 0; for (int i = 1; i < prices.size(); i++) { result += max(prices[i] - prices[i - 1], 0); } return result; } };  55. 跳跃游戏 跳几步重要，考虑最大的...

将问题分解为若干个子问题 找出适合的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解  这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。 455.分发饼干 大胃口先吃大饼干（for胃口，if饼干，不能反过来否则胃口太大，一个饼干都满足不了直接跳过了）和小饼干给小胃口吃（for饼干，if胃口,不能反过来，否饼干太小满足不了最小的胃口也会跳过）都可以 //C++ 先分配小饼干 class Solution { public: int findContentChil...

今天的三道题重点掌握N皇后，二刷看其他两道。 332.重新安排行程（hard） 一刷搞清楚几个问题就行，容器的使用这有点麻烦。   一个行程中，如果航班处理不好容易变成一个圈，成为死循环。 先遍历记录所有机场能够走的次数，利用次数>0避免循环,如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 使用map记录顺序 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？结果集的大小 = 机票数量 + 1 代表所机票涵盖的有机场（可能有重复...

491.递增子序列 和子集类似，但不能排序去重，也就不能通过挨着的元素树层去重。  求子集，子序列都是在节点上收获结果（回溯可以不要终止条件，找到结果也不需要return），而划分，分割都是在叶子节点上获得结果，注意区分，组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。 求子集不需要终止条件，搜到底就结束了。 注意Uset仅是一层的局部变量，不需要回溯，和used数组去重需要回溯不一样，因为used是一个全局变量（通过引用传参）  //C++ class Solution { public: vector<vector<int>>...

93.复原IP地址 还是分割字符串类型的，不过path集合是一个完整的string，还要加.,注意size是会动态变化的。  用.来分割，由于path是完整的（当然也可以用vector存最后合并，我一开始就是这么做的），要用,的数量pointNum进行终止条件的判断 和day25 17.电话号码的字母组合一样，终止条件里 == s.size 要往下一位才结束 像这种string转int的，stoll还是有可能超，遍历string数组累加求和是最好的。  //C++ 自己想的，就是判断是否合理那先导0处理的不是很好 class Solution { public: vector<strin...

39. 组合总和 自己想的代码对，但单层搜索逻辑不够清晰，别背，注意回溯index的起始如果是从数组里面挑从0开始，而不是前面的题1~9从1开始。  //C++ class Solution { public: vector<vector<int>> result; vector<int> path; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { BackTracking(target, candidates, 0...

216.组合总和III 一样是回溯三部曲，区别在于这次每个节点的集合是固定的1~0，剪枝为所求和大于target就return。  确定终止条件 如果path.size() == k相，就终止。如果此时path里收集到的元素和（sum） 和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。 单层搜索过程 path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和。处理过程和回溯过程是一一对应的，处理有加，回溯就要有减！可以通过每次都计算和免去回溯Sum，但path是要回溯的。  //C++ class Solution { public: v...