20210827 每日总结

1. python细节：

   • 回溯法把每一层的结果放入总结果result时，要用切片的方式复制append(path[:])，否则仅仅是引用了path的地址，会随着path不断变化

2. 回溯法复习

   • 组合问题：参数StartIndex 控制每一层遍历数组里的下一个数字。
     • 组合总和，无重复元素情况下：元素不能重复拿，每次递归从startindex+1开始；可以重复拿就从startindex开始。
     • 组合总和2，有重复元素情况下：元素只能拿一次，且不能出现相同组合，意味着同一树层上不能重复，同一树枝上可以重复，需要一个used数组判断前一个相同的数字是否用过（某数和前数相等且前数的used为初始状态，则同层使用过）
   • LC17电话号码组合问题：需要一个index来控制遍历不同的数字（即遍历的深度）；而每个数字对应的3-4个字母是每一层遍历的广度（由本层的for循环控制），终止条件就是深度参数idx等于规定的长度。每次递归传入idx+1表示处理下一个数字。
   • 切割问题：startIdx模拟切割线，对[startIdx：i+1]子串进行递归遍历、判断、回溯。
   • 子集问题：要保存的是所有节点而非仅仅是叶子结点。写法上的区别在于：不需要结束条件，递归收集所有节点，for循环结束自动结束
   • LC491.递增子序列：与组合总和2相似，都是数组有重复且不允许结果重复。组合问题可以排序+标记来去重，此题牵扯到递增，不能排序，单开一个数组记录本层哪些数字访问过。
   • 排列问题：
     • 无重复的数组的全排列，和组合问题的不同就是每次递归都从0开始遍历，用used数组来保证不会重复选到自己，体现在代码上就是组合问题的used数组可以放在递归函数内，每一个新分支都重置；而排列问题used数组放在递归函数外，保证每个分支往深处递归时不停的更新。
     • 有重复的数组的全排列，要求结果不能重复，这就说明同一树层和同一树枝上的元素都不能重复。综合前面的去重方法，用used[i-1] 和 used[i]来判断。

3. 动态规划 子序列子串问题复习

   • 最长递增子序列：因为要求可以不连续，故而dp[i] 依赖于从0-i-1的最长子序列长度+1。
   • 最长连续递增子序列：要求必须连续，故而dp[i] 只依赖于dp[i-1] +1 ，初始化都为1。
   • 最长重复子数组：要求必须连续，定义dp[i][j] 为A下标0-i-1、B下标0-j-1的子串的最长公共子数组长度，只依赖于dp[i-1][j-1]
   • 最长公共子序列：要求不一定连续，分类讨论当A[i-1][j-1]和B[i-1][j-1]相等和不相等（不相等时i j依赖于i-1 j和i j-1的最大值）