子数组的最大累加和问题（贪心） 题意 给一个数字数组，求子数组和的最大值 思路分析 对于长度大于1的任意答案，考虑能否从这个答案眼花出更优的答案 如果答案选择数组两端有负数  那么把负数去掉，会得到更大的答案，所以两端一定都不是负数 如果答案两端外还有正数  那么包含这些正数，会得到更大的答案，所以答案的两端外一定都是非正数 如果答案一侧数组和为负数  去掉这一侧，会得到更大的答案  综上，答案选出的是一个 非正[非负 ... 非负] 非正 的子数组，且单侧部分数组和不为负 左侧为负 用变量cnt 记录从上一个选中的 非正[非负到目前位置的总和 如果数组左侧子数组为负，则cnt < 0直...

买卖股票的最好时机(三)（动态规划） 题意 数值数组,最多两次买卖,两次买卖不重叠,问最大收益 思路分析 状态设计 主要有数组遍历下标和买卖状态 所以不妨设状态为[下标][买的次数][卖的次数]=当前最大收益 递推关系 注意到两次买卖不重叠,所以卖的次数+1>=买的次数>=卖的次数, 同时也可以知道,如果两个次数相等,最后一次发生的是卖,如果买次数更大,最后一次发生的是买 if(j == k){ // 卖 dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1] + prices[i]); }else if(j > k){ // 买 dp[...

把数字翻译成字符串（动态规划） 题意 给定一个数字串,它是由a-z映射成1-26得到的,问它的原文有多少种可能 思路分析 能被反向的条件 因为是a-z映射成1-26得到的 所以每个被反向映射的值一定在1-26之间 所以判断是1位还是2位,且值满足范围,没有前导0 能被反向的1位数 只有1-9可以被反向编译 所以 nums[i] != '0'  能被反向的2位数 10-26可以被反向 nums[i-1] != '0' && (nums[i-1]-'0')*10+(nums[i]-'0') <= 26  递推关系 设dp[i]表示从开始到第i位能被反向的方案数那么有 if(可...

矩阵的最小路径和（动态规划） 题意 给定一个二维0/1数组,求由1构成的最大的正方形是多少 思路分析 题意转换 把问题转换,变成给你同样的数组,你可以从任何0值出发,向右,向下,或向右下走,记录每个格子所需要的最少步数 求最少步数的最大值 证明等价 转换后的题意,意味着每个1的格子的值,表示的是它左上方最近的0格子和它的距离 也就是以这个格子为右下角所产生的正方形的最大边长, 边长的平方就是要求的面积, 和题意等价 递推公式 那么有递推公式 if(matrix[i][j] == 0) continue/return; // 不处理为0的情况 if(matrix[i-1][j] == 0 || ...

矩阵的最小路径和（动态规划） 题意 给定一个二维数字数组,求从左上角,走到右下角,路径上值的最小和 思路分析 相邻关系 如果走到最后路径和最小,那么它上一步来源是上方或者左方 int f(i,j){ return min(f(i-1,j),f(i,j-1)) + matrix[i][j]; }  递归转递推 对于任意一个位置,走到它的最小值是唯一的 把上面的递归式子反向改为递推 for(int i = 0;i<matrix.size();i++){ for(int j = 0;j<matrix[0].size();j++){ dp[i][j] = min(dp[i-1][j],dp...

编辑距离(二)（动态规划） 题意 给定两个字符串,把字符串str1编辑为str2的最小代价,其中插入(ic),删除(dc)和替换(rc)代价分别为给定常数 思路分析 顺序性无关证明 设对str1有一系列操作, 对于一个被增加的字符,一定不会被删除和被修改 对于一个被删除的字符,一定不会被增加和被修改 对一个修改出的字符,一定不会被增加和删除 这些操作相对于最终结果来说,调整顺序对结果无影响. 也就是不妨设所有操作从左到右依次执行 上一步关系 那么如果我们通过操作让str1和str2相等了 按照下标考虑,如果str1最后一个字符和str2一致, 那么不操作的代价最低,如何把str1[:-1]变为...

最长公共子子串（动态规划） 题意 给定两个字符串,求它们的最长公共子串 思路分析 公共子串 要找s1和s2的公共子串,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的后缀公共子串加上相等的字符,就能得到一个更长的公共子串, 所以有, 令s[i][j]表示分别匹配到i,j的一个公共序列 for(int i = 0; i < s1.length();i++){ for(int j = 0;j < s2.length();j++){ if(s1[i] == s2[j]){ // 匹配字符 s[i][j] = s[i-1][j-1] + s1[i...

动态规划用法总结（二） 动态规划是一个相对高级的工具，有些本身是动态规划的题可以用动态规划以外，当你无法一眼看穿最优解法时，你可以考虑直接使用动态规划。 动态规划最常见的解法思路步骤是  设计状态 设计转移方程 对转移方程时间空间优化 大多数可以改写为递推 边界处理 实现  优点是，基于状态和状态转移，空间复杂度时间复杂度在完全思考前容易预估计，状态一般与输入参数大小直接相关，容易设计，常见的贪心类的，堆栈类的有不少可以用动态规划实现。同时当实现完后，在优化过程中，可能可以推出最优解法。 当然伴随的缺点也是，可能比最优解法在时空复杂度会相对更高 技巧  一维状态转移  state[i] = f...

最长公共子序列(二)（动态规划） 题意 给定两个字符串,求它们的最长公共序列 思路分析 公共序列 要找s1和s2的公共序列,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的公共序列加上相等的字符,就能得到一个更长的公共序列, 所以有, 令s[i][j]表示分别匹配到i,j的一个公共序列 for(int i = 0; i < s1.length();i++){ for(int j = 0;j < s2.length();j++){ if(s1[i] == s2[j]){ // 匹配字符 s[i][j] = s[i-1][j-1] + s1[...

最长上升子序列(三)（动态规划） 题意 给定一个正整数数组，求它的最长上升子序列，如果有多个，求数值字典序最小的 思路分析 上升子序列 先不考虑最长，先考虑如何找到一个上升子序列 每次对于一个值，去找它前面比它小的值就能构成 最后把链输出就能得到上升子序列 for(int i = 0;i<arr.size();i++){ int j = i-1; while(j >= 0 && arr[j] >= arr[i])j--; // 忽略掉 大于等于 当前值的 prei[i] = j; // 建立链表 指向一个比它小的位置 }  这样每个pre[i]指向了一个比i位...

兑换零钱（一）（动态规划） 题意 给定一个正整数数组，和一个目标值，问最少选取多少个数组中的值能使得其和等于目标值。其中每个值可以被选任意次 思路分析 最优关系的数学推导  假设对于值aim有一个最优方案，这个最优方案中有选一次x,那么 上述最优方案中去掉x的剩余的数，是aim-x的一个最优方案。 证明： 反证法，如果去掉x后不是aim-x的最优方案，也就是存在更优的方案，让aim-x有更少数量的构成，那么对于这个让aim-x有更少数量构成的方案，加上x,也会让aim有更优方案。与初始方案是aim的最优方案矛盾 综上, 一个最优方案，一定是由某个最优方案，加上某个值得到的 转换成表达式 这里我...

最长回文子串（遍历） 题意 给定字符串中最长回文子串有多长 思路分析 判断回文串 对于是不是回文串，可以通过从字符串的两边开始比较对称位置 for(int i = 0;i < s.length();i++){ if(s[i] != s[s.length()-1-i])return false; } return true;  从中心向两侧判断 如果把方向改一改，从字符串的中心位置向两边搜索 int n = s.length(); for(int i = 0;i < n/2;i++){ if(s[n/2-1-i] != s[n-n/2+i])return false; } retur...

子数组最大乘积（贪心） 题意 一个有正负和零的double数组中，最大的子数组乘积为多少 思路分析 快速运算乘积 如果数组中没有零 计算数组一段的乘积，相当于计算从数组起始到结束的乘积，除以起始到数组开始之前的积 f(i,j) = premul[j] / premul[i-1]  局部最优  对于选中的结束位置j,我们要让f(i,j) 尽量大，则premul[i-1]的绝对值尽量小，且和它同号。 如果一正一负，取正值即可，不会发生运算。 零值 如果有零，零相当于把数组的分界线，只要乘积跨越了零始终是零，所以只用考虑被零值划分出的一个个小数组 状态维护 按符号不同分别维护，同符号的绝对值最小值 ...

动态规划用法总结（一） 动态规划是一个相对高级的工具，有些本身是动态规划的题可以用动态规划以外，当你无法一眼看穿最优解法时，你可以考虑直接使用动态规划。 动态规划最常见的解法思路步骤是  设计状态 设计转移方程 对转移方程时间空间优化 大多数可以改写为递推 边界处理 实现  优点是，基于状态和状态转移，空间复杂度时间复杂度在完全思考前容易预估计，状态一般与输入参数大小直接相关，容易设计，常见的贪心类的，堆栈类的有不少可以用动态规划实现。同时当实现完后，在优化过程中，可能可以推出最优解法。 当然伴随的缺点也是，可能比最优解法在时空复杂度会相对更高 技巧  一维状态转移  state[i] = f...