刷了六七十道题一百题多题，发现每次遇到数据结构以外的题都略吃力，一般脑子里想的都是如何递归，分解成小问题，但子结构和解的关系各不相同。多遇到几题之后，又觉得其实题目都是有规律的。总之感觉是很费脑子的一些东西，有些题刚背完又忘记一些小细节，反反复复的出错，果真是错误具有重复性。断断续续刷了快一个半月了想想自己刷题速度是真的慢，只能自己心里假装安慰一下，起码还算学了点什么，没有一事无成。

常见题目中，分治法（Divide and Conquer）以及动态规划(Dynamic Programming)这种思想用的很多，递归/迭代只是一种实现这种方式的思想。遇到问题，什么时候用分治，什么时候用动态规划，以及结题时的框架。先对这几种思想理论上学习，再结合剑指offer里面的例题做一个分析（感觉光剑指Offer远远不够，还需要找其他的学习或者视频资料，比如geekforgeeks，剑指offer的题目还是太少了，而且不够的系统，整个刷下来再回过去看剑指offer的题，发现原来觉得很难的现在觉得简单了不少），对这几种算法有一个大致还算清楚的认识。

分治 Divide and Conquer

分治法基础

自顶向下

1. 将问题分解为若干个规模较小的相同问题，最优子结构性质（什么叫最优子结构？），于是可以递归。
2. 子问题的解可以合并为该问题的解。如果不满足可以考虑动态规划或者贪心
3. 该问题所分解出的各个子问题是相互独立的，子问题之间不包含公共的子子问题（有点拗口啊），如果子问题是不独立的分治则需要做许多其它的工作，重复的解公共子问题虽然可用分治法，但一般用动态规划更好。涉及到分治的效率
4. 分治法虽然看起来有那么点条条框框，很规整，目前刷了大概二十题典型的例题后，发现还是很有规律的。
   • 分治法一个典型的例子就是二分法，有很多变种题型，但总体的框架无非为不断的折半缩小查找的范围，难点出现在如何移动左边界和右边界，此时要根据题意仔细确认，比如search in a rotated sorted array。
   • 分治法第二个典型的例子就是二叉树，左子树，右子树，此类题掌握规律之后很简单，唯一一点的小难点也不过是设计helper函数算出子结果，然后merge子结果，常见换锅汤没换药的题型有 找到最大子树的平均数/找最长连续路径/找最大/最小/或者深度相关的。

算法设计模式

Divide-and-Conquer(P)
  if |P|<= n0:
    return DirectSolve(P)
  # split the problem into several sub-problem
  for i in range(k):
    Problem.append(P_k)
  # solve the subproblem
  for i in range(k):
    y.append(divide-and-Conquer(P_k))
  # merge the answer
 return merge(y[:])

分治法复杂性分析

分解成k个规模为n/m的子问题,merge 需要f(n)时间，则有

例题分析

1. 分治思想的两大经典例题 Binary Search和Merge Sort. 两个都是将大问题分成两半。其中mergeSort的merge步骤需要开辟额外的空间储存中间的结果。
2. 关于二分法，好用的编程模板是 mid=start+(end-start)/2 while(start+1<end)，然后最后再分别判断start 和end里有没有包含解。
3. 分治法中分解为小问题的时候，要构建好helper函数。

二分查找的例题

此类例题一般给出的数组是有序或者是循环数组，变种题包括进阶版的2dMatrix。

描述：假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。

你需要找到其中最小的元素。

分析：最小的数的特点，递减。故不断二分缩小范围即可。

Sqrt(x)例题，平方根的例题

描述：实现 int sqrt(int x) 函数，计算并返回 x 的平方根。

分析： 二分查找，时间复杂度log(x)，比顺序查找好。

描述：计算a^n % b，其中a，b和n都是32位的非负整数

分析：n是32位的整数，由指数爆炸可知，直接结算不可行。故直接二分 n/2 n/2-1来做，但同时还是要很小心溢出。但此种递归的写法时间很长，不是太可取,接近超时，故如果扩展的话要考虑非递归的写法。

class Solution {
    public:
    int fastPower(int a, int b, int n) {
        if (n == 1) {
            return a % b;
        }
        if (n == 0) {
            return 1 % b;
        }
        
        long product = fastPower(a, b, n / 2);
        product = (product * product) % b;
        if (n % 2 == 1) {
            product = (product * a) % b;
        }
        return (int) product;
    }
};

这种相似的写法直接超时，无法通过

class Solution {
public:
    int fastPower(int a, int b, int n) {
      return helper(a,b,n);
    }
    
    long helper(int a,int b, int n){
        if(n==0){return 1%b;}
        if(n==1){return a%b;}
        
         long left = helper(a,b,n/2);
        long right = helper(a,b,n-n/2);
         
        return (left*right)%b;
    }
   
};

WoodCut :

描述：有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。

分析: 也是二分，从1开始找起

Copy Books

描述：给出一个数组A包含n个元素，表示n本书以及各自的页数。现在有个k个人复印书籍，每个人只能复印连续一段编号的书，比如A[1],A[2]由第一个人复印，但是不能A[1],A[3]由第一个人复印，求最少需要的时间复印所有书。

分析： 二分查找， K 个compacity

BFS宽度优先搜索

BFS宽度优先搜索，主要用的数据结构为queue，规避DFS中不断递归递归栈的大小。BFS不是第一次接触这种算法，之前学图的时候曾经还算比较深入的学习过这种算法，故这次学起来的时候不太吃力。

BFS的系统学习参考了九章算法里面的视频，讲的很清楚细致，总结来说就是，按层遍历，标记遍历过的点，每次放入队列的时候都要标记visited过。

出现的题目有 树的分层遍历，图的遍历，以及变种题，矩阵往上走，往下走。

C++中用到的记录是否visited的数据结构有  set<T>,map<T,T>

经典题目

拓扑排序类题目

描述：你需要去上n门九章的课才能获得offer，这些课被标号为 0 到 n-1 。
有一些课程需要“前置课程”，比如如果你要上课程0，你需要先学课程1，我们用一个匹配来表示他们： [0,1]

给你课程的总数量和一些前置课程的需求，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

同样是课程表但是却不是拓扑排序的题

描述：这里有 n 门不同的线上课程, 编号为 1 到 n. 每一节课都有持续时间(课程长度) t 和 在第 d 天关闭. 课程应连续持续 t 天，必须在第d天或之前完成, 你将从第一天开始.
给出 n 门线上课程用 pairs (t, d) 来表示, 你的任务是找到可以上的最大数量的课程数.

给出 [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
返回 3

遍历类题目

图是否是一棵树

分析：**图是树的条件

• 边为n-1条，没有环
• 是全联通的
• 从一个点出发遍历即可

Clone Graph 克隆图

分析：同样也是建立在遍历的基础上，按照BFS遍历的思路，但是难点在要把原节点和新的节点用一个HashMap关联起来，这样遍历到边的时候才知道哪个顶点连接哪个顶点。

骑士/僵尸/矩阵类等最短路径类题目

描述：给定骑士在棋盘上的 初始 位置(一个2进制矩阵 0 表示空 1 表示有障碍物)，找到到达 终点 的最短路线，返回路线的长度。如果骑士不能到达则返回 -1 。

分析： 最短路径的一种做法为BFS遍历，最先找到的即为最短路径，是一道很简单的题目。

找到联通区域类的题目

给一个二维的矩阵，包含 'X' 和 'O', 找到所有被 'X' 围绕的区域，并用 'X' 填充满。

分析： 也是建立在遍历的基础上，可用DFS也可以用BFS，不过DFS可能递归的深度会比较深。

DFS深度优先搜索

DFS之前虽然也说接触过，但只是在图的遍历中接触过。但是它比如回溯却很少接触到。刚开始做DFS的题目还很吃力，主要是回溯那一块，如何到下一个状态，如何记录已经访问过的状态（去重），需要不断的思考以及参考别人的答案。

DFS在图的遍历中很简单，直接应用栈即可，但是在回溯中，现在有两个比较经典的问题，一个是带重复字符的排列permutation，一个是带重复数字的combination问题。这两个问题是想了很久才想通的问题（榆木脑袋感觉自己老了），就这两个问题写一下自己的思路。（如何巧妙的去重而不是很暴力的用hashmap记录）

先排序！！！这两种特殊类型的题目都建立在排好序的基础上。 核心思想是每次只选第一次出现的，剩下的跳过。

1. combination 问题，可以抽象为从第一个元素递归，到最后一个元素为结束，可以选或者不选。画Recursion Tree分析重复状态，然后只选第一次出现的分支。

   下面为一种求子集的programming paradigm, 每个状态都是一种答案，然后如果不是第一次出现，则不扩展。helper函数的理解：以subRes为开头的所有的解，递归结束条件，到达end的时候，所以用了一个for循环，以及每一个状态都是一个subset，一个解。

class Solution {
public:
    vector<vector<int >> subsetsWithDup(vector<int> &nums) {
        // write your code here
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;

        subsetsHelper(nums,0,{},res);
        return res;
    }

private:
    void subsetsHelper(vector<int>&nums,int start,vector<int> subRes,vector<vector<int >>& res){
        // true select false not select
        res.push_back(subRes);
        for (int i = start; i <nums.size() ; ++i) {
            if (i!=start&&nums[i]==nums[i-1]){
                continue;
            }
                subRes.push_back(nums[i]);
                subsetsHelper(nums,i+1,subRes,res);
                subRes.pop_back();
        }
    }
};

1. Combination Sum问题给出一组候选数字(C)和目标数字(T),找出C中所有的组合，使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。

   给出一个例子，候选数字集合为[10,1,6,7,2,1,5] 和目标数字 8 ,

   解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]

   分析：为上题的变种，如果每个数字智能使用一次的话，则依旧是每次挑选候选的数字，但是加入判断条件。

   为了巩固的时候，此题用python重写一遍，却在subRes[:]和subRes此处，导致一直出错，一定要注意。如果用subRes，remove element的时候却用了[:-1]用了深拷贝，所以上一层指向的内存区域却没有递减，导致出错。如果用pop(),则每一次返回包括start+1都要pop一次，也会导致问题。我们要认清楚这个DFS的过程，每次沿着某一深度找答案，找不到，则返回上一个状态，所以用deepcopy来存储上一个状态！

   测试用例（[1,1,2,3],4）,此后要分开一个章节python和C++写不同的地方。

   class Solution:
       def combinationSum2(self, num, target):
           # write your code here
           num.sort()
           result=[]
           self.helper(num,0,[],target,result)
           return result
       def helper(self,num,start,subRes,target,res):
   
           if(target==0):
               res.append(subRes[:])
               return
           if(start>=len(num)):
               return
           for i in range(start,len(num)):
               if(i!=start and num[i]==num[i-1]):
                   continue
               if(target<num[i]):
                   break
               subRes.append(num[i])
               # 一开始此题用的是subRes而不是subRes，结果一直出错。这的确是Python和C++的不同，一定要多加小心和注意各种的引用！！！
               self.helper(num,i+1,subRes[:],target-num[i],res)
               subRes = subRes[:-1]
   

2. permutation问题，和combination不同的是，每一个元素都要参与进来，同时每一种排列又都是结果，一般判断是否要swap。同时，和combination一样，也存在去重的问题，只取第一个。 helper函数的理解： 以该字母为开头的所有的排列。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        // write your code here
        if (nums.size() == 0) {
            return {{}};
        }
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        helper(nums, 0, res);
        return res;
    }
private:
    void helper(vector<int> &nums, int start, vector<vector<int>>& res) {
        if (start>=nums.size()){
            res.push_back(nums);
            return;
        }
        helper(nums,start+1,res);
        for (int i = start+1; i < nums.size(); ++i) {
            if (i!=start+1&&nums[i]== nums[i-1]){
                continue;
            }
            if (nums[i]!=nums[start]){
                swap(nums[start],nums[i]);
                helper(nums,start+1,res);
                swap(nums[start],nums[i]);
            }
        }
    }
};

动态规划Dynamic Programming

动态规划基础

每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

与分治法的不同：经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解），把子问题的解保存在表格里，当再次解决此问题时，常数时间。

1.最优子结构（Optimal Substructure Property）：当问题的最优解包含了子问题的最优解时，称该问题具有最优子结构。 递归，能用子问题的最优解。
2.重叠子问题（overlapping subproblems）：在递归求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。画一下recursion tree可以判断

常见题型：

• 求最大值最小值
• 判断是否可行
• 统计方案个数（而不是给出所有的具体方案）

不是动态规划：

• 求具体所有方案
• 输入是一个集合，而不是序列（没有相对位置的关系）
• 时间复杂度是多项式n^2,n3

算法设计模式

1. 确定是DP问题（最优子结构+重叠子问题） maximize or minimize certain quantity or counting problems，最大化最小化或者计数问题。时间复杂度不是n^2, n^3, 不是多项式，而是指数形式。
2. 写出状态公式（难点）
3. 应用自顶向下或者自底向上

**自顶向下备忘录模式:Memoization Method – Top Down Dynamic Programming **

应用递归的方式，每次递归的时候，查找结果是否保存，保存，直接应用，没保存，计算，并保存。

1. 状态之间的转移很容易想到

2. 计算慢，因为递归

3. 只需要计算需要计算的子问题，不必计算所有的子问题。

   递归的几个要素，1.递归的函数定义（接收什么，输出什么，返回什么）2. 递归什么时候结束 3. 如何将大问题拆解为小问题。

# using a DP to save the result of subproblem
DP[MaxN]
DP(P):
  if(|P|<n0):
    D[P] = DirectSolve(P)
    return D[P]
  elif(DP(P) is calculated):
    return DP[P]
  else:
    DP[P]=stateTransistion(D[:P-1])
    return DP[P]  

自底向上动态规划:**Tabulation Method – Bottom Up Dynamic Programming **

1. 状态之间的转移有时候没有那么明显，代码有时候有点复杂，因为要处理多种条件
2. 从小问题开始，一步步解决大问题。

先求出最小子问题的解，然后一步步直到求解到大问题。

# using a DP to save the result of subproblem
DP(P):
  DP[MaxN]
  DP[0] = DirectSolve(P0)
  for i in range(1,n):
    DP[i] = stateTransistion(D[:P-1])

动态规划例题

动态规划的难点，一：有时候状态隐藏的很深，不知道有哪些状态 二：有时候比较难找到状态的转移方程。这点目前的想法是通过多做题，来寻找一些邪乎的解题的灵感。

动态规划目前常见的题型有

1. 矩阵坐标型
2. 序列型
   • 单序列 LIS题及变种
   • 双序列 LCS longgest common subsequence
3. Knapsack问题的变种 数硬币
4. 划分型
5. 区间 难，比如optimal BST,矩阵相乘

参考过的资料 geekforgeeks上面讲的动态规划，LintCode上面动态规划的题目。

目前看过的视频

• youtube上青云算法动态规划/图灵教主
  • knapsack with repetition的bottom up/top down解法
  • knapsack without repetition 的bottom up/top down解法
• 九章算法动态规划
  • 坐标型动态规划
  • 接龙型动态规划

动态规划坐标型的例题

Triangle

描述：给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

[
 [2],
 [3,4],
 [6,5,7],
 [4,1,8,3]
]

分析： 关键字，最小路径和，而并没有要给出所有最小路径。初始状态 dp[0][0],终止状态 dp[row-1][].状态之间的转移 dp[i][j] = min{dp[i-1][j-1],dp[i-1][j]],dp[i+1][j]}+A[i][j]

状态很简单，状态转移也很简单,直接写代码即可。

描述：给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径

分析：换汤不换药，不过移动的方向不一样了，自顶向下和自底向上两种方式都很好写，优先选用非递归方式。

描述：有一个机器人的位于一个 m × n 个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径？

分析：第一个想法，应该是排列组合的数学方法，直接计算出结果

但如果要动态规划，同样也是左边和上面路径个数之和

单序列接龙型

要求后面的能和前面接上，比如比前面的大，比如是前面的和。是一维数组，答案可以由前面的序列得出，所以要进行扫描

LIS longest increasing subsequence

描述：给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

给出 [5,4,1,2,3]，LIS 是 [1,2,3]，返回 3
给出 [4,2,4,5,3,7]，LIS 是 [2,4,5,7]，返回 4

描述：给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。
给出 n = 13, 返回 2 因为 13 = 4 + 9。

类似题：丑数，catalan数，fibbonacci数，bell number数

描述：给一个由 无重复的正整数 组成的集合，找出满足任意两个元素 (Si, Sj) 都有 Si % Sj = 0 或 Sj % Si = 0 成立的最大子集。

给一个数组 [1,2,3]，返回 [1,2] 或 [1,3]
给一个数组 [1,2,4,8]，返回 [1,2,4,8]

描述：给一定数量的信封，带有整数对 (w, h) 分别代表信封宽度和高度。一个信封的宽高均大于另一个信封时可以放下另一个信封。求最大的信封嵌套层数。

给一些信封 [[5,4],[6,4],[6,7],[2,3]] ，最大的信封嵌套层数是 3([2,3] => [5,4] => [6,7])。

记录AC过程： 该题可以说是longest increasing subsequence的变种，是leetcode和lintcode一道hard的题。 动态规划的思路不难想，很快也就做出来了。但是在模仿LIS O(logn)的写法时，没有看答案的时候感觉已经到智商的极限了。 大概提交了差不多有十遍都没有AC。主要不AC的原因在于处理同一宽度不同信封高度时候逻辑不够清楚（知道现在逻辑还是不够清楚:( ）。 做不出来的时候一直心情很糟，很焦虑，想吃零食，一会躺躺一会听听歌企图有新思路，但是一切都太徒劳。大概前前后后都栽了七八个小时在这题上了，主要还是在死钻牛角尖。 对这种状态也有了新的思考，下次遇到这个问题的时候如何一下子跳出怪圈，如何证明这种想法是错的，而不是在试探？？

分析： 主体思路和LIS差不多，但是关键的核心点在于： 同一宽度逆序排列。贴一贴示例代码。

class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        // write your code here
        vector<int> dp;
        auto cmp=[](pair<int,int>&a,pair<int,int>&b){
            return a.first<b.first||(a.first==b.first&&a.second>b.second);
        };
        sort(envelopes.begin(),envelopes.end(),cmp);      
        for(auto p:envelopes){
           // 省去折半查找的过程 lower_bound函数，应该记录一下
            auto it = lower_bound(dp.begin(),dp.end(),p.second);
            if(it==dp.end()) {dp.push_back(p.second);}else{
                *it = p.second;
            }
        }        
        return dp.size();
    }
};

描述：

一只青蛙正要过河，这条河分成了 x 个单位，每个单位可能存在石头，青蛙可以跳到石头上，但它不能跳进水里。
按照顺序给出石头所在的位置，判断青蛙能否到达最后一块石头所在的位置。刚开始时青蛙在第一块石头上，假设青蛙第一次跳只能跳一个单位的长度。
如果青蛙最后一个跳 k 个单位，那么它下一次只能跳 k - 1 ，k 或者 k + 1 个单位。注意青蛙只能向前跳。

给出石头的位置为 [0,1,3,5,6,8,12,17]

总共8块石头。
第一块石头在 0 位置，第二块石头在 1 位置，第三块石头在 3 位置等等......
最后一块石头在 17 位置。

返回 true。青蛙可以通过跳 1 格到第二块石头，跳 2 格到第三块石头，跳 2 格到第四块石头，跳 3 格到第六块石头，跳 4 格到第七块石头，最后跳 5 格到第八块石头。

给出石头的位置为 `[0,1,2,3,4,8,9,11]`
返回 false。青蛙没有办法跳到最后一块石头因为第五块石头跟第六块石头的距离太大了。

分析：总觉得这题是宽度优先搜索，也尝试用了宽度优先搜索来做，但是超时了。 状态转移方程不难找，但是，什么是重复子问题？会有重复子问题么？ 什么时候为false？

Knapsack问题

Knapsack不带重复

0-1背包问题，不带重复，求最多能装多少价值？

Input:

W[i]: 第i件物品的重量

V[i]: 第i件物品的价值

C： 背包的容量。

初始状态: 容量为C，总价值为0，一件物品也没拿, 最终达到value最大。

故我们可以从第一件物品开始，选择拿或者不拿，到最后一个物品结束。

拿 dp[i][c-w[i]], 不拿 dp[i][c]. 两种之间的最大值，而且c-w[i]>=0。Bottem up 和top down两种写法都不难。 从i=0->所有物品

Knapsack带重复

如果每个东西可以重复的拿，则每次都应该从0开始到最后一个物品，逐一每次选价值最大的。

dp[i] = max{dp[i-w[j]]}

题外话

1. 可用贪心么？ 九章算法里面说，不管怎样都能举出反例，0-1背包问题没有贪心解法.
2. 相似问题，国王挖黄金，换硬币问题

近日来的一些题外话，所谓书抄百遍，其义自现，做的题太少了，所以每次还是抓耳挠腮一不小心就钻进死胡同里了，钻进死胡同里还爱往墙上撞，不停的试探以及提交企图AC而不是工工整整的分析好思路，愚蠢的暴力解决，感觉最近要触到从地下室往上走的第一层天花板了，有时候晚上八点五分左右骑车从图书馆往家里骑的时候都会觉得心塞塞。每回那个时间点都要上坡经过一个桥，然后有时候会伏着身子猛的冲刺然后下坡的时候挺直腰也不蹬想些东西，想自己要干什么，往上还看到有投简历各种岗位不瞎投一波是不是过几个月就要凉凉各种公司都没有hc。

昨晚突然有个朋友说要帮我内推苹果，我估摸了一下自己，现在去八成是分母了。看了一眼是做NLP的，NLP是觉得挺有意思的，但….0….经验，没论文，调参都没调过。躺床上翻懒翻去目前这个半吊子状态不去当分母了。翻来翻去上回下了功夫去做一件事情是大三考雅思，差不多将近三个月，那个时候每天都吃很多，可能是现在饭量的1.5倍还多，人还是瘦了差不多六七斤。

不知道自己是不是在闭门造车，但是不太仔细的评估了一下，想到达大概LintCode刷完300题，Java 和C++两门语言能了解特性而不是会写几行代码，就算明年真的缩招到剩烂白菜也不会说一些马后炮的“我要是当时xxxxx，我就xxxx。”

有效率的有计划的刷LintCode/LeetCode 300题，有自己的执念，也不闭门造车，以及再次感谢家中老爸老妈的包容提供吃喝。希望以后提起这段人生经历还会觉得很有意思吧，从找销售服务岗不用上下班打卡谨言慎行说什么话都要婉转的岗位突然跳到程序员。

突然想起考雅思前两天还是三天的时候，晚自习回来眼泪巴巴的和尚香哭，说自己考不过，诶呦，西湖水呀我的泪，现在想想蛮有意思的。

感觉应该在给自己一些压力，怎么着还是太松散，几百题啥时候才能很有心得体会的刷完啊，还得刷百遍其义自见呢