算法中文手册
[toc]
NAS上搭建SS客户端
群辉NAS上搭建SS客户端来连接远程并提供本地HTTP/Socks5代理
**Contents** [hide](https://1024.ee/index.php/2020/04/06/群辉nas上搭建ss客户端来连接远程并提供本地http-socks5代理/#)
下载docker – ss-privoxy
高级设置
注意是文件，不是文件夹。而且，文件名就是config, 不是config.conf之类。
1 | #配置文件 |
设置端口
- 7070 For Socks5 – All Traffic
- 8118 for Http/Https – 部分域名翻墙，改conf文件即可
最后查一查
开启后查查日志，一切正常即可
群辉自己的使用，开这里就行。
指令
1 | docker run -d --restart=always \ |
动态规划答疑篇
动态规划答疑篇
预计阅读时间：7 分钟
这篇文章就给你讲明白两个读者问得最多的问题：
1、到底什么才叫「最优子结构」，和动态规划什么关系。
2、为什么动态规划遍历dp数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历，有的无论咋遍历都是对的。
一、最优子结构详解
「最优子结构」是某些问题的一种特定性质，并不是动态规划问题专有的。也就是说，很多问题其实都具有最优子结构，只是其中大部分不具有重叠子问题，所以我们不把它们归为动态规划系列问题而已。
我先举个很容易理解的例子：假设你们学校有 10 个班，你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩，你会不会算？当然会，而且你不用重新遍历全校学生的分数进行比较，而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。
我给你提出的这个问题就符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。
你看，这么简单的问题都有最优子结构性质，只是因为显然没有重叠子问题，所以我们简单地求最值肯定用不出动态规划。
再举个例子：假设你们学校有 10 个班，你已知每个班的最大分数差（最高分和最低分的差值）。那么现在我让你计算全校学生中的最大分数差，你会不会算？可以想办法算，但是肯定不能通过已知的这 10 个班的最大分数差推到出来。因为这 10 个班的最大分数差不一定就包含全校学生的最大分数差，比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差。
这次我给你提出的问题就不符合最优子结构，因为你没办通过每个班的最优值推出全校的最优值，没办法通过子问题的最优值推出规模更大的问题的最优值。前文 动态规划详解 说过，想满足最优子结，子问题之间必须互相独立。全校的最大分数差可能出现在两个班之间，显然子问题不独立，所以这个问题本身不符合最优子结构。
那么遇到这种最优子结构失效情况，怎么办？策略是：改造问题。对于最大分数差这个问题，我们不是没办法利用已知的每个班的分数差吗，那我只能这样写一段暴力代码：
1 | int result = 0; |
改造问题，也就是把问题等价转化：最大分数差，不就等价于最高分数和最低分数的差么，那不就是要求最高和最低分数么，不就是我们讨论的第一个问题么，不就具有最优子结构了么？那现在改变思路，借助最优子结构解决最值问题，再回过头解决最大分数差问题，是不是就高效多了？
当然，上面这个例子太简单了，不过请读者回顾一下，我们做动态规划问题，是不是一直在求各种最值，本质跟我们举的例子没啥区别，无非需要处理一下重叠子问题。
前文 动态规划：不同的定义产生不同的解法 和 经典动态规划：高楼扔鸡蛋（进阶篇） 就展示了如何改造问题，不同的最优子结构，可能导致不同的解法和效率。
再举个常见但也十分简单的例子，求一棵二叉树的最大值，不难吧（简单起见，假设节点中的值都是非负数）：
1 | int maxVal(TreeNode root) { |
你看这个问题也符合最优子结构，以root为根的树的最大值，可以通过两边子树（子问题）的最大值推导出来，结合刚才学校和班级的例子，很容易理解吧。
当然这也不是动态规划问题，旨在说明，最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质；但反过来，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的，以后碰到那种恶心人的最值题，思路往动态规划想就对了，这就是套路。
动态规划不就是从最简单的 base case 往后推导吗，可以想象成一个链式反应，不断以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质。
找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。这也是套路，经常刷题的朋友应该能体会。
这里就不举那些正宗动态规划的例子了，读者可以翻翻历史文章，看看状态转移是如何遵循最优子结构的，这个话题就聊到这，下面再来看另外个动态规划迷惑行为。
二、dp 数组的遍历方向
我相信读者做动态规划问题时，肯定会对dp数组的遍历顺序有些头疼。我们拿二维dp数组来举例，有时候我们是正向遍历：
1 | int[][] dp = new int[m][n]; |
有时候我们反向遍历：
1 | for (int i = m - 1; i >= 0; i--) |
有时候可能会斜向遍历：
1 | // 斜着遍历数组 |
甚至更让人迷惑的是，有时候发现正向反向遍历都可以得到正确答案，比如我们在 团灭 LeetCode 股票买卖问题 中有的地方就正反皆可。
那么，如果仔细观察的话可以发现其中的原因的。你只要把住两点就行了：
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置。
下面来具体解释上面两个原则是什么意思。
比如编辑距离这个经典的问题，详解见前文 经典动态规划：编辑距离，我们通过对dp数组的定义，确定了 base case 是dp[..][0]和dp[0][..]，最终答案是dp[m][n]；而且我们通过状态转移方程知道dp[i][j]需要从dp[i-1][j],dp[i][j-1],dp[i-1][j-1]转移而来，如下图：
那么，参考刚才说的两条原则，你该怎么遍历dp数组？肯定是正向遍历：
1 | for (int i = 1; i < m; i++) |
因为，这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的，而且最终结束在我们想要的答案dp[m][n]。
再举一例，回文子序列问题，详见前文 子序列解题模板：最长回文子序列，我们通过过对dp数组的定义，确定了 base case 处在中间的对角线，dp[i][j]需要从dp[i+1][j],dp[i][j-1],dp[i+1][j-1]转移而来，想要求的最终答案是dp[0][n-1]，如下图：
这种情况根据刚才的两个原则，就可以有两种正确的遍历方式：
要么从左至右斜着遍历，要么从下向上从左到右遍历，这样才能保证每次dp[i][j]的左边、下边、左下边已经计算完毕，最终得到正确结果。
现在，你应该理解了这两个原则，主要就是看 base case 和最终结果的存储位置，保证遍历过程中使用的数据都是计算完毕的就行，有时候确实存在多种方法可以得到正确答案，可根据个人口味自行选择。
动态规划设计之最长递增子序列
动态规划设计之最长递增子序列
预计阅读时间： 9 分钟
很多读者反应，就算看了前文 动态规划详解，了解了动态规划的套路，也不会写状态转移方程，没有思路，怎么办？本文就借助「最长递增子序列」来讲一种设计动态规划的通用技巧：数学归纳思想。
最长递增子序列（Longest Increasing Subsequence，简写 LIS）是比较经典的一个问题，比较容易想到的是动态规划解法，时间复杂度 O(N^2)，我们借这个问题来由浅入深讲解如何写动态规划。
比较难想到的是利用二分查找，时间复杂度是 O(NlogN)，我们通过一种简单的纸牌游戏来辅助理解这种巧妙的解法。
先看一下题目，很容易理解：
注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的。下面先来一步一步设计动态规划算法解决这个问题。
一、动态规划解法
动态规划的核心设计思想是数学归纳法。
相信大家对数学归纳法都不陌生，高中就学过，而且思路很简单。比如我们想证明一个数学结论，那么我们先假设这个结论在 k<n 时成立，然后想办法证明 k=n 的时候此结论也成立。如果能够证明出来，那么就说明这个结论对于 k 等于任何数都成立。
类似的，我们设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 dp[0…i−1] 都已经被算出来了，然后问自己：怎么通过这些结果算出dp[i] ?
直接拿最长递增子序列这个问题举例你就明白了。不过，首先要定义清楚 dp 数组的含义，即 dp[i] 的值到底代表着什么？
我们的定义是这样的：****dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
举个例子：
算法演进的过程是这样的：
根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。
1 | int res = 0; |
读者也许会问，刚才这个过程中每个 dp[i] 的结果是我们肉眼看出来的，我们应该怎么设计算法逻辑来正确计算每个 dp[i] 呢？
这就是动态规划的重头戏了，要思考如何进行状态转移，这里就可以使用数学归纳的思想：
我们已经知道了 d**p[0…4] 的所有结果，我们如何通过这些已知结果推出 d**p[5] 呢？
根据刚才我们对 dp 数组的定义，现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。
nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。
当然，可能形成很多种新的子序列，但是我们只要最长的，把最长子序列的长度作为 dp[5] 的值即可。
_20210715223303.gif)
这段代码的逻辑就可以算出 dp[5]。到这里，这道算法题我们就基本做完了。读者也许会问，我们刚才只是算了 dp[5] 呀，dp[4], dp[3] 这些怎么算呢？
类似数学归纳法，你已经可以通过 dp[0…4] 算出 dp[5] 了，那么任意 dp[i] 你肯定都可以算出来：
还有一个细节问题，就是 base case。dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1。下面我们看一下完整代码：
至此，这道题就解决了，时间复杂度 O(N^2)。总结一下动态规划的设计流程：
首先明确 dp 数组所存数据的含义。这步很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
然后根据 dp 数组的定义，运用数学归纳法的思想，假设 d**p[0…i−1] 都已知，想办法求出 d**p[i]，一旦这一步完成，整个题目基本就解决了。
但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。
二、二分查找解法
这个解法的时间复杂度会将为 O(NlogN)，但是说实话，正常人基本想不到这种解法（也许玩过某些纸牌游戏的人可以想出来）。所以如果大家了解一下就好，正常情况下能够给出动态规划解法就已经很不错了。
根据题目的意思，我都很难想象这个问题竟然能和二分查找扯上关系。其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关，甚至有一种排序方法就叫做 patience sorting（耐心排序）。
为了简单起见，后文跳过所有数学证明，通过一个简化的例子来理解一下思路。
首先，给你一排扑克牌，我们像遍历数组那样从左到右一张一张处理这些扑克牌，最终要把这些牌分成若干堆。
处理这些扑克牌要遵循以下规则：
只能把点数小的牌压到点数比它大的牌上。如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去。如果当前牌有多个堆可供选择，则选择最左边的堆放置。
比如说上述的扑克牌最终会被分成这样 5 堆（我们认为 A 的值是最大的，而不是 1）。
为什么遇到多个可选择堆的时候要放到最左边的堆上呢？因为这样可以保证牌堆顶的牌有序（2, 4, 7, 8, Q），证明略。
按照上述规则执行，可以算出最长递增子序列，牌的堆数就是我们想求的最长递增子序列的长度，证明略。
我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗，牌堆顶的牌不是有序吗，这就能用到二分查找了：用二分查找来搜索当前牌应放置的位置。
PS：旧文 二分查找算法详解 详细介绍了二分查找的细节及变体，这里就完美应用上了。如果没读过强烈建议阅读。
至此，二分查找的解法也讲解完毕。
这个解法确实很难想到。首先涉及数学证明，谁能想到按照这些规则执行，就能得到最长递增子序列呢？其次还有二分查找的运用，要是对二分查找的细节不清楚，给了思路也很难写对。
所以，这个方法作为思维拓展好了。但动态规划的设计方法应该完全理解：假设之前的答案已知，利用数学归纳的思想正确进行状态的推演转移，最终得到答案。
回溯算法团灭排列组合子集问题
回溯算法团灭排列/组合/子集问题
回溯算法团灭排列/组合/子集问题
预计阅读时间：7 分钟
今天就来聊三道考察频率高，而且容易让人搞混的算法问题，分别是求子集（subset），求排列（permutation），求组合（combination）。这几个问题都可以用回溯算法解决。
一、子集
问题很简单，输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集。
1 | vector<vector<int>> subsets(vector<int>& nums); |
比如输入 nums = [1,2,3]，你的算法应输出 8 个子集，包含空集和本身，顺序可以不同：
[ [],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3] ]
第一个解法是利用数学归纳的思想：假设我现在知道了规模更小的子问题的结果，如何推导出当前问题的结果呢？
具体来说就是，现在让你求 [1,2,3] 的子集，如果你知道了 [1,2] 的子集，是否可以推导出 [1,2,3] 的子集呢？先把 [1,2] 的子集写出来瞅瞅：
[ [],[1],[2],[1,2] ]
你会发现这样一个规律：
subset([1,2,3]) - subset([1,2])
= [3],[1,3],[2,3],[1,2,3]
而这个结果，就是把 sebset([1,2]) 的结果中每个集合再添加上 3。
换句话说，如果 A = subset([1,2]) ，那么：
subset([1,2,3])
= A + [A[i].add(3) for i = 1..len(A)]
这就是一个典型的递归结构嘛，[1,2,3] 的子集可以由 [1,2] 追加得出，[1,2] 的子集可以由 [1] 追加得出，base case 显然就是当输入集合为空集时，输出子集也就是一个空集。
翻译成代码就很容易理解了：
1 | vector<vector<int>> subsets(vector<int>& nums) { |
这个问题的时间复杂度计算比较容易坑人。我们之前说的计算递归算法时间复杂度的方法，是找到递归深度，然后乘以每次递归中迭代的次数。对于这个问题，递归深度显然是 N，但我们发现每次递归 for 循环的迭代次数取决于 res 的长度，并不是固定的。
根据刚才的思路，res 的长度应该是每次递归都翻倍，所以说总的迭代次数应该是 2^N。或者不用这么麻烦，你想想一个大小为 N 的集合的子集总共有几个？2^N 个对吧，所以说至少要对 res 添加 2^N 次元素。
那么算法的时间复杂度就是 O(2^N) 吗？还是不对，2^N 个子集是 push_back 添加进 res 的，所以要考虑 push_back 这个操作的效率：
1 | vector<vector<int>> res = ... |
因为 res[i] 也是一个数组呀，push_back 是把 res[i] copy 一份然后添加到数组的最后，所以一次操作的时间是 O(N)。
综上，总的时间复杂度就是 O(N*2^N)，还是比较耗时的。
空间复杂度的话，如果不计算储存返回结果所用的空间的，只需要 O(N) 的递归堆栈空间。如果计算 res 所需的空间，应该是 O(N*2^N)。
第二种通用方法就是回溯算法。旧文「回溯算法详解」写过回溯算法的模板：
1 | result = [] |
只要改造回溯算法的模板就行了：
1 | vector<vector<int>> res; |
可以看见，对 res 的更新是一个前序遍历，也就是说，res 就是树上的所有节点：
二、组合
输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合。
1 | vector<vector<int>> combine(int n, int k); |
比如输入 n = 4, k = 2，输出如下结果，顺序无所谓，但是不能包含重复（按照组合的定义，[1,2] 和 [2,1] 也算重复）：
[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]
这就是典型的回溯算法，k 限制了树的高度，n 限制了树的宽度，直接套我们以前讲过的回溯算法模板框架就行了：
1 | vector<vector<int>>res; |
backtrack 函数和计算子集的差不多，区别在于，更新 res 的地方是树的底端。
三、排列
输入一个不包含重复数字的数组 nums，返回这些数字的全部排列。
1 | vector<vector<int>> permute(vector<int>& nums); |
比如说输入数组 [1,2,3]，输出结果应该如下，顺序无所谓，不能有重复：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
回溯算法详解 中就是拿这个问题来解释回溯模板的。这里又列出这个问题，是将「排列」和「组合」这两个回溯算法的代码拿出来对比。
首先画出回溯树来看一看：
我们当时使用 Java 代码写的解法：
1 | List<List<Integer>> res = new LinkedList<>(); |
回溯模板依然没有变，但是根据排列问题和组合问题画出的树来看，排列问题的树比较对称，而组合问题的树越靠右节点越少。
在代码中的体现就是，排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字。
以上，就是排列组合和子集三个问题的解法，总结一下：
子集问题可以利用数学归纳思想，假设已知一个规模较小的问题的结果，思考如何推导出原问题的结果。也可以用回溯算法，要用 start 参数排除已选择的数字。
组合问题利用的是回溯思想，结果可以表示成树结构，我们只要套用回溯算法模板即可，关键点在于要用一个 start 排除已经选择过的数字。
排列问题是回溯思想，也可以表示成树结构套用算法模板，不同之处在于使用 contains 方法排除已经选择的数字，前文有详细分析，这里主要是和组合问题作对比。
对于这三个问题，关键区别在于回溯树的结构，不妨多观察递归树的结构，很自然就可以理解代码的含义了。
回溯算法和动态规划，到底谁是谁爹
回溯算法和动态规划，到底谁是谁爹？
我们前文经常说回溯算法和递归算法有点类似，有的问题如果实在想不出状态转移方程，尝试用回溯算法暴力解决也是一个聪明的策略，总比写不出来解法强。
那么，回溯算法和动态规划到底是啥关系？它俩都涉及递归，算法模板看起来还挺像的，都涉及做「选择」，真的酷似父与子。
那么，它俩具体有啥区别呢？回溯算法和动态规划之间，是否可能互相转化呢？
今天就用力扣第 494 题「目标和」来详细对比一下回溯算法和动态规划，真可谓群魔乱舞：
注意，给出的例子 nums 全是 1，但实际上可以是任意正整数哦。
一、回溯思路
其实我第一眼看到这个题目，花了两分钟就写出了一个回溯解法。
任何算法的核心都是穷举，回溯算法就是一个暴力穷举算法，前文 回溯算法解题框架 就写了回溯算法框架：
1 | def backtrack(路径, 选择列表): |
关键就是搞清楚什么是「选择」，而对于这道题，「选择」不是明摆着的吗？
**对于每个数字 nums[i]，我们可以选择给一个正号 + 或者一个负号 -**，然后利用回溯模板穷举出来所有可能的结果，数一数到底有几种组合能够凑出 target 不就行了嘛？
伪码思路如下：
1 | def backtrack(nums, i): |
如果看过我们之前的几篇回溯算法文章，这个代码可以说是比较简单的了：
1 | int result = 0; |
有的读者可能问，选择 - 的时候，为什么是 rest += nums[i]，选择 + 的时候，为什么是 rest -= nums[i] 呢，是不是写反了？
不是的，「如何凑出 target」和「如何把 target 减到 0」其实是一样的。我们这里选择后者，因为前者必须给 backtrack 函数多加一个参数，我觉得不美观：
1 | void backtrack(int[] nums, int i, int sum, int target) { |
因此，如果我们给 nums[i] 选择 + 号，就要让 rest - nums[i]，反之亦然。
以上回溯算法可以解决这个问题，时间复杂度为 O(2^N)，N 为 nums 的大小。这个复杂度怎么算的？回忆前文 学习数据结构和算法的框架思维，发现这个回溯算法就是个二叉树的遍历问题：
1 | void backtrack(int[] nums, int i, int rest) { |
树的高度就是 nums 的长度嘛，所以说时间复杂度就是这棵二叉树的节点数，为 O(2^N)，其实是非常低效的。
那么，这个问题如何用动态规划思想进行优化呢？
二、消除重叠子问题
动态规划之所以比暴力算法快，是因为动态规划技巧消除了重叠子问题。
如何发现重叠子问题？看是否可能出现重复的「状态」。对于递归函数来说，函数参数中会变的参数就是「状态」，对于 backtrack 函数来说，会变的参数为 i 和 rest。
前文 动态规划之编辑距离 说了一种一眼看出重叠子问题的方法，先抽象出递归框架：
1 | void backtrack(int i, int rest) { |
举个简单的例子，如果 nums[i] = 0，会发生什么？
1 | void backtrack(int i, int rest) { |
你看，这样就出现了两个「状态」完全相同的递归函数，无疑这样的递归计算就是重复的。这就是重叠子问题，而且只要我们能够找到一个重叠子问题，那一定还存在很多的重叠子问题。
因此，状态 (i, rest) 是可以用备忘录技巧进行优化的：
1 | int findTargetSumWays(int[] nums, int target) { |
以前我们都是用 Python 的元组配合哈希表 dict 来做备忘录的，其他语言没有元组，可以用把「状态」转化为字符串作为哈希表的键，这是一个常用的小技巧。
这个解法通过备忘录消除了很多重叠子问题，效率有一定的提升，但是这就结束了吗？
三、动态规划
事情没有这么简单，先来算一算，消除重叠子问题之后，算法的时间复杂度是多少？其实最坏情况下依然是 O(2^N)。
为什么呢？因为我们只不过恰好发现了重叠子问题，顺手用备忘录技巧给优化了，但是底层思路没有变，依然是暴力穷举的回溯算法，依然在遍历一棵二叉树。这只能叫对回溯算法进行了「剪枝」，提升了算法在某些情况下的效率，但算不上质的飞跃。
其实，这个问题可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题。动态规划总是这么玄学，让人摸不着头脑……
首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：
1 | sum(A) - sum(B) = target |
综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：**nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2**？
类似的子集划分问题我们前文 经典背包问题：子集划分 讲过，现在实现这么一个函数：
1 | /* 计算 nums 中有几个子集的和为 sum */ |
然后，可以这样调用这个函数：
1 | int findTargetSumWays(int[] nums, int target) { |
好的，变成背包问题的标准形式：
有一个背包，容量为 sum，现在给你 N 个物品，第 i 个物品的重量为 nums[i - 1]（注意 1 <= i <= N），每个物品只有一个，请问你有几种不同的方法能够恰好装满这个背包？
现在，这就是一个正宗的动态规划问题了，下面按照我们一直强调的动态规划套路走流程：
第一步要明确两点，「状态」和「选择」。
对于背包问题，这个都是一样的，状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。
第二步要明确 dp 数组的定义。
按照背包问题的套路，可以给出如下定义：
dp[i][j] = x 表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。
翻译成我们探讨的子集问题就是，若只在 nums 的前 i 个元素中选择，若目标和为 j，则最多有 x 种方法划分子集。
根据这个定义，显然 dp[0][..] = 0，因为没有物品的话，根本没办法装背包；dp[..][0] = 1，因为如果背包的最大载重为 0，「什么都不装」就是唯一的一种装法。
我们所求的答案就是 dp[N][sum]，即使用所有 N 个物品，有几种方法可以装满容量为 sum 的背包。
第三步，根据「选择」，思考状态转移的逻辑。
回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态 dp[i-1][j]，继承之前的结果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么只要看前 i - 1 个物品有几种方法可以装满 j - nums[i-1] 的重量就行了，所以取决于状态 dp[i-1][j-nums[i-1]]。
PS：注意我们说的 i 是从 1 开始算的，而数组 nums 的索引时从 0 开始算的，所以 nums[i-1] 代表的是第 i 个物品的重量，j - nums[i-1] 就是背包装入物品 i 之后还剩下的容量。
由于 dp[i][j] 为装满背包的总方法数，所以应该以上两种选择的结果求和，得到状态转移方程：
1 | dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]; |
然后，根据状态转移方程写出动态规划算法：
1 | /* 计算 nums 中有几个子集的和为 sum */ |
然后，发现这个 dp[i][j] 只和前一行 dp[i-1][..] 有关，那么肯定可以优化成一维 dp：
1 | /* 计算 nums 中有几个子集的和为 sum */ |
对照二维 dp，只要把 dp 数组的第一个维度全都去掉就行了，唯一的区别就是这里的 j 要从后往前遍历，原因如下：
因为二维压缩到一维的根本原理是，dp[j] 和 dp[j-nums[i-1]] 还没被新结果覆盖的时候，相当于二维 dp 中的 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]。
那么，我们就要做到：在计算新的 dp[j] 的时候，dp[j] 和 dp[j-nums[i-1]] 还是上一轮外层 for 循环的结果。
如果你从前往后遍历一维 dp 数组，dp[j] 显然是没问题的，但是 dp[j-nums[i-1]] 已经不是上一轮外层 for 循环的结果了，这里就会使用错误的状态，当然得不到正确的答案。
现在，这道题算是彻底解决了。
总结一下，回溯算法虽好，但是复杂度高，即便消除一些冗余计算，也只是「剪枝」，没有本质的改进。而动态规划就比较玄学了，经过各种改造，从一个加减法问题变成子集问题，又变成背包问题，经过各种套路写出解法，又搞出状态压缩，还得反向遍历。
现在搞得我都忘了自己是来干嘛的了。嗯，这也许就是动态规划的魅力吧。
如何拆解复杂问题：实现一个计算器
如何拆解复杂问题：实现一个计算器
我记得很多大学数据结构的教材上，在讲栈这种数据结构的时候，应该都会用计算器举例，但是有一说一，讲的真的垃圾，我只感受到被数据结构支配的恐惧，丝毫没有支配数据结构的快感。
不知道多少未来的计算机科学家就被这种简单的数据结构劝退了。
1、输入一个字符串，可以包含+ - * / ()``、数字、空格，你的算法返回运算结果。
2、要符合运算法则，括号的优先级最高，先乘除后加减。
3、除号是整数除法，无论正负都向 0 取整（5/2=2，-5/2=-2）。
4、可以假定输入的算式一定合法，且计算过程不会出现整型溢出，不会出现除数为 0 的意外情况。
比如输入如下字符串，算法会返回 9：
1 | 3 * (2-6 /(3 -7)) |
可以看到，这就已经非常接近我们实际生活中使用的计算器了，虽然我们以前肯定都用过计算器，但是如果简单思考一下其算法实现，就会大惊失色：
1、按照常理处理括号，要先计算最内层的括号，然后向外慢慢化简。这个过程我们手算都容易出错，何况写成算法呢！
2、要做到先乘除，后加减，这一点教会小朋友还不算难，但教给计算机恐怕有点困难。
3、要处理空格。我们为了美观，习惯性在数字和运算符之间打个空格，但是计算之中得想办法忽略这些空格。
那么本文就来聊聊怎么实现上述一个功能完备的计算器功能，关键在于层层拆解问题，化整为零，逐个击破，相信这种思维方式能帮大家解决各种复杂问题。
下面就来拆解，从最简单的一个问题开始。
一、字符串转整数
是的，就是这么一个简单的问题，首先告诉我，怎么把一个字符串形式的正整数，转化成 int 型？
1 | string s = "458"; |
这个还是很简单的吧，老套路了。但是即便这么简单，依然有坑：**(c - '0')的这个括号不能省略，否则可能造成整型溢出**。
因为变量c是一个 ASCII 码，如果不加括号就会先加后减，想象一下n如果接近 INT_MAX，就会溢出。所以用括号保证先减后加才行。
二、处理加减法
现在进一步，如果输入的这个算式只包含加减法，而且不存在空格，你怎么计算结果？我们拿字符串算式1-12+3为例，来说一个很简单的思路：
1、先给第一个数字加一个默认符号+，变成+1-12+3。
2、把一个运算符和数字组合成一对儿，也就是三对儿+1，-12，+3，把它们转化成数字，然后放到一个栈中。
3、将栈中所有的数字求和，就是原算式的结果。
我们直接看代码，结合一张图就看明白了：
1 | int calculate(string s) { |
我估计就是中间带switch语句的部分有点不好理解吧，**i就是从左到右扫描，sign和num跟在它身后。**当s[i]遇到一个运算符时，情况是这样的：
所以说，此时要根据sign的 case 不同选择nums的正负号，存入栈中，然后更新sign并清零nums记录下一对儿符合和数字的组合。
另外注意，不只是遇到新的符号会触发入栈，当i走到了算式的尽头（i == s.size() - 1），也应该将前面的数字入栈，方便后续计算最终结果。
至此，仅处理紧凑加减法字符串的算法就完成了，请确保理解以上内容，后续的内容就基于这个框架修修改改就完事儿了。
三、处理乘除法
其实思路跟仅处理加减法没啥区别，拿字符串2-3*4+5举例，核心思路依然是把字符串分解成符号和数字的组合。
比如上述例子就可以分解为+2，-3，*4，+5几对儿，我们刚才不是没有处理乘除号吗，很简单，其他部分都不用变，在switch部分加上对应的 case 就行了：
1 | for (int i = 0; i < s.size(); i++) { |
乘除法优先于加减法体现在，乘除法可以和栈顶的数结合，而加减法只能把自己放入栈。
现在我们思考一下****如何处理字符串中可能出现的空格字符。其实也非常简单，想想空格字符的出现，会影响我们现有代码的哪一部分？
1 | // 如果 c 非数字 |
显然空格会进入这个 if 语句，但是我们并不想让空格的情况进入这个 if，因为这里会更新sign并清零nums，空格根本就不是运算符，应该被忽略。
那么只要多加一个条件即可：
1 | if ((!isdigit(c) && c != ' ') || i == s.size() - 1) { |
好了，现在我们的算法已经可以按照正确的法则计算加减乘除，并且自动忽略空格符，剩下的就是如何让算法正确识别括号了。
四、处理括号
处理算式中的括号看起来应该是最难的，但真没有看起来那么难。
为了规避编程语言的繁琐细节，我把前面解法的代码翻译成 Python 版本：
1 | def calculate(s: str) -> int: |
这段代码跟刚才 C++ 代码完全相同，唯一的区别是，不是从左到右遍历字符串，而是不断从左边pop出字符，本质还是一样的。
那么，为什么说处理括号没有看起来那么难呢，因为括号具有递归性质。我们拿字符串3*(4-5/2)-6举例：
1 | calculate(`3*(4-5/2)-6`) |
可以脑补一下，无论多少层括号嵌套，通过 calculate 函数递归调用自己，都可以将括号中的算式化简成一个数字。换句话说，括号包含的算式，我们直接视为一个数字就行了。
现在的问题是，递归的开始条件和结束条件是什么？遇到(开始递归，遇到)结束递归：
1 | def calculate(s: str) -> int: |
你看，加了两三行代码，就可以处理括号了，这就是递归的魅力。至此，计算器的全部功能就实现了，通过对问题的层层拆解化整为零，再回头看，这个问题似乎也没那么复杂嘛。
五、最后总结
本文借实现计算器的问题，主要想表达的是一种处理复杂问题的思路。
我们首先从字符串转数字这个简单问题开始，进而处理只包含加减法的算式，进而处理包含加减乘除四则运算的算式，进而处理空格字符，进而处理包含括号的算式。
可见，对于一些比较困难的问题，其解法并不是一蹴而就的，而是步步推进，螺旋上升的。如果一开始给你原题，你不会做，甚至看不懂答案，都很正常，关键在于我们自己如何简化问题，如何以退为进。
退而求其次是一种很聪明策略。你想想啊，假设这是一道考试题，你不会实现这个计算器，但是你写了字符串转整数的算法并指出了容易溢出的陷阱，那起码可以得 20 分吧；如果你能够处理加减法，那可以得 40 分吧；如果你能处理加减乘除四则运算，那起码够 70 分了；再加上处理空格字符，80 有了吧。我就是不会处理括号，那就算了，80 已经很 OK 了好不好。
我们要支配算法，而不是被算法支配。如果这种思维方式对大家有些启发，希望点个在看分享。
子序列解题模板：最长回文子序列
子序列解题模板：最长回文子序列
预计阅读时间：6 分钟
子序列问题是常见的算法问题，而且并不好解决。
首先，子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举都不容易，更别说求解相关的算法问题了。
而且，子序列问题很可能涉及到两个字符串，比如让你求两个字符串的 最长公共子序列，如果没有一定的处理经验，真的不容易想出来。所以本文就来扒一扒子序列问题的套路，其实就有两种模板，相关问题只要往这两种思路上想，十拿九稳。
一般来说，这类问题都是让你求一个最长子序列，因为最短子序列就是一个字符嘛，没啥可问的。一旦涉及到子序列和最值，那几乎可以肯定，**考察的是动态规划技巧，时间复杂度一般都是 O(n^2)**。
原因很简单，你想想一个字符串，它的子序列有多少种可能？起码是指数级的吧，这种情况下，不用动态规划技巧，还想怎么着呢？
既然要用动态规划，那就要定义 dp 数组，找状态转移关系。我们说的两种思路模板，就是 dp 数组的定义思路。不同的问题可能需要不同的 dp 数组定义来解决。
一、两种思路
1、****第一种思路模板是一个一维的 dp 数组：
1 | int n = array.length; |
举个我们写过的例子 最长递增子序列，在这个思路中 dp 数组的定义是：
*在子数组array[0..i]中，以*array[i]**结尾的目标子序列（最长递增子序列）的长度是dp[i]**。
为啥最长递增子序列需要这种思路呢？前文说得很清楚了，因为这样符合归纳法，可以找到状态转移的关系，这里就不具体展开了。
2、****第二种思路模板是一个二维的 dp 数组：
1 | int n = arr.length; |
这种思路运用相对更多一些，尤其是涉及两个字符串/数组的子序列。本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况。
2.1 涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：
**在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列（最长公共子序列）长度为dp[i][j]**。
2.2 只涉及一个字符串/数组时（比如本文要讲的最长回文子序列），dp 数组的含义如下：
**在子数组array[i..j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]**。
第一种情况可以参考这两篇旧文：详解编辑距离 和 最长公共子序列。
下面就借最长回文子序列这个问题，详解一下第二种情况下如何使用动态规划。
二、最长回文子序列
之前解决了 最长回文子串 的问题，这次提升难度，求最长回文子序列的长度：
我们说这个问题对 dp 数组的定义是：**在子串s[i..j]中，最长回文子序列的长度为dp[i][j]**。一定要记住这个定义才能理解算法。
为啥这个问题要这样定义二维的 dp 数组呢？我们前文多次提到，找状态转移需要归纳思维，说白了就是如何从已知的结果推出未知的部分，这样定义容易归纳，容易发现状态转移关系。
具体来说，如果我们想求dp[i][j]，假设你知道了子问题dp[i+1][j-1]的结果（s[i+1..j-1]中最长回文子序列的长度），你是否能想办法算出dp[i][j]的值（s[i..j]中，最长回文子序列的长度）呢？
可以！这取决于s[i]和s[j]的字符：
如果它俩相等，那么它俩加上s[i+1..j-1]中的最长回文子序列就是s[i..j]的最长回文子序列：
如果它俩不相等，说明它俩不可能同时出现在s[i..j]的最长回文子序列中，那么把它俩分别加入s[i+1..j-1]中，看看哪个子串产生的回文子序列更长即可：
以上两种情况写成代码就是这样：
1 | if (s[i] == s[j]) |
至此，状态转移方程就写出来了，根据 dp 数组的定义，我们要求的就是dp[0][n - 1]，也就是整个s的最长回文子序列的长度。
三、代码实现
首先明确一下 base case，如果只有一个字符，显然最长回文子序列长度是 1，也就是dp[i][j] = 1,(i == j)。
因为i肯定小于等于j，所以对于那些i > j的位置，根本不存在什么子序列，应该初始化为 0。
另外，看看刚才写的状态转移方程，想求dp[i][j]需要知道dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1]这三个位置；再看看我们确定的 base case，填入 dp 数组之后是这样：
为了保证每次计算dp[i][j]，左、下、左下三个方向的位置已经被计算出来，只能斜着遍历或者反着遍历：
我选择反着遍历，代码如下：
1 | int longestPalindromeSubseq(string s) { |
至此，最长回文子序列的问题就解决了。
主要还是正确定义 dp 数组的含义，遇到子序列问题，首先想到两种动态规划思路，然后根据实际问题看看哪种思路容易找到状态转移关系。
另外，找到状态转移和 base case 之后，一定要观察 DP table，看看怎么遍历才能保证通过已计算出来的结果解决新的问题
有了以上思路方向，子序列问题也不过如此嘛。
完全二叉树的节点数，你真的会算吗？
完全二叉树的节点数，你真的会算吗？
如果让你数一下一棵普通二叉树有多少个节点，这很简单，只要在二叉树的遍历框架上加一点代码就行了。
但是，如果给你一棵完全二叉树，让你计算它的节点个数，你会不会？算法的时间复杂度是多少？
这个算法的时间复杂度应该是 O(logN*logN)，如果你心中的算法没有达到这么高效，那么本文就是给你写的。
首先要明确一下两个关于二叉树的名词「完全二叉树」和「满二叉树」。
我们说的完全二叉树如下图，每一层都是紧凑靠左排列的：
我们说的满二叉树如下图，是一种特殊的完全二叉树，每层都是是满的，像一个稳定的三角形：
说句题外话，关于这两个定义，中文语境和英文语境似乎有点区别，我们说的完全二叉树对应英文 Complete Binary Tree，没有问题。但是我们说的满二叉树对应英文 Perfect Binary Tree，而英文中的 Full Binary Tree 是指一棵二叉树的所有节点要么没有孩子节点，要么有两个孩子节点。如下：
以上定义出自 wikipedia，这里就是顺便一提，其实名词叫什么都无所谓，重要的是算法操作。
本文就按我们中文的语境，记住「满二叉树」和「完全二叉树」的区别，等会会用到。
一、思路分析
现在回归正题，如何求一棵完全二叉树的节点个数呢？
1 | // 输入一棵完全二叉树，返回节点总数 |
如果是一个普通二叉树，显然只要向下面这样遍历一边即可，时间复杂度 O(N)：
1 | public int countNodes(TreeNode root) { |
那如果是一棵满二叉树，节点总数就和树的高度呈指数关系，时间复杂度 O(logN)：
1 | public int countNodes(TreeNode root) { |
完全二叉树比普通二叉树特殊，但又没有满二叉树那么特殊，计算它的节点总数，可以说是普通二叉树和完全二叉树的结合版，先看代码：
1 | public int countNodes(TreeNode root) { |
结合刚才针对满二叉树和普通二叉树的算法，上面这段代码应该不难理解，就是一个结合版，但是其中降低时间复杂度的技巧是非常微妙的。
二、复杂度分析
开头说了，这个算法的时间复杂度是 O(logN*logN)，这是怎么算出来的呢？
直觉感觉好像最坏情况下是 O(N*logN) 吧，因为之前的 while 需要 logN 的时间，最后要 O(N) 的时间向左右子树递归：
1 | return 1 + countNodes(root.left) + countNodes(root.right); |
关键点在于，这两个递归只有一个会真的递归下去，另一个一定会触发hl == hr而立即返回，不会递归下去。
为什么呢？原因如下：
一棵完全二叉树的两棵子树，至少有一棵是满二叉树：
看图就明显了吧，由于完全二叉树的性质，其子树一定有一棵是满的，所以一定会触发hl == hr，只消耗 O(logN) 的复杂度而不会继续递归。
综上，算法的递归深度就是树的高度 O(logN)，每次递归所花费的时间就是 while 循环，需要 O(logN)，所以总体的时间复杂度是 O(logN*logN)。
所以说，「完全二叉树」这个概念还是有它存在的原因的，不仅适用于数组实现二叉堆，而且连计算节点总数这种看起来简单的操作都有高效的算法实现。
快慢指针的一些证明
快慢指针在链表中的一些证明
目录
一、一定会相遇的证明
二、环长度
三、连接点
四、带环链表总长度
五、例题
一、一定会相遇的证明
证明1
1、如果链表没有环，那么快指针比慢指针先到达尾部（null)。
2、如果链表有环的话，因为快指针走的比慢指针快，所以在环中相遇的过程可以看作是快指针从环后边追赶慢指针的过程。
用递归法证明，快慢指针一定会相遇：
（1)快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
（2)快指针与慢指针之间差两步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。
（3)快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)即N-1步。重复这个过程，直到快指针和慢指针相遇。
因此，此题得证。所以快指针必然与慢指针相遇。
证明2
如果链表存在环，快慢指针就一定能相遇。设快指针每次移动q步，慢指针每次移动s步，环的长度为n，环之前的链表长度为m，如下图所示
假设慢指针第一次到达环时移动了x次，位置为a，此时快指针也移动了x次，位置为b，
则此时快慢指针相遇的等式为，
也即（1）成立，
又：
（2），
（3），
由（1）（2）（3）可得出成立，显而易见（q(x+y)-s(x+y) == n *k(k=1,2,3,…)），x+y是n的整数倍的时候，该式一定成立。
————————————————找环的起点分割线——————————————
假设快指针每次移动2步，慢指针每次移动1步，则根据上述证明可知，，
，相遇的位置在y处；求环的起点，就是求m的大小，此时令一指针p1从头结点出发，每次移动1步，令一指针q1从相遇处出发，每次移动1步，则p1与q1再次相遇的地方就是环的起点处，因为此时两个指针均移动m步，由
可知，相遇
推导：慢指针进入环后，快指针最多多绕一个圈。
快指针F先进环，慢指针S后进。
假设慢指针进环那一刻快指针差m步能追上（0<= m < Length环），根据上边结论，两个指针走m次就会相遇了。
因为m < Length环，所以快指针在慢指针进环那一刻最多比慢指针多绕一个圈。
二、环长度
快指针和慢指针第一次相遇时的节点pq（碰撞点），快指针和慢指针从该点开始继续往前走，再次碰撞时所用的操作数就是环的长度Length环。
证明:由上边的推导可得，这里的m为Lengh环。
三、连接点
假设慢指针进入环中时，即连接点p，快指针（q）需要m步才能追上慢指针。
p和q第一次相遇时，碰撞点在pq处。此时，p走到pq时用了m步。
假设head到p的距离为a，环长度为Length环，慢指针走了s步，则快指针走了2s步。
从上图可知:
s = a + m
2s = a + m + n * Length环（n为快指针绕环的圈数）
可得
a = n * Length环 - m
也就是：若在头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点p。
可根据这个结论来找到入口节点。
四、带环链表总长度
找到连接点p后，求head到p的长度，再加上环的长度，即为链表的总长。