先介绍暴力递归，然后逐步学习到动态规划的题目
1. 暴力递归
暴力递归就是尝试
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件(base case)
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
1.1 汉诺塔问题
题目描述:
打印n层汉诺塔问题，从最左边移动到最右边的全部过程。
解法:
这个问题的解，属于2^N复杂度，采用递归方法解决。在起初采用自然解法时，需要填充6个字函数，最后通过观察发现，可以统一成一个函数:
1). 把1～N-1 从 from->other
2). N(自己) 从 from->to
3). 1～N-1 从 other->to
// 一共要补齐六个这样的函数，不过经过观察可以发现规律
// 若想要 from -> to
// 先把 N-1 from -> other
// 再把 N from-> to
// 最后再把 N-1 other -> to
// 1~i 圆盘 目标是from -> to， other是另外一个
public static void process(int N, String from, String to, String other) {
if(N==1){
System.out.println("Move 1 from " + from + " to " + to);
return;
}
process(N-1, from, other, to);
System.out.println("Move " + N + " from " + from + " to " + to);
process(N-1, other, to, from);
}
public static void call_process(int N){
if(N>0){
process(N, "左", "右", "中");
}else{
throw new IllegalArgumentException("N should be greater than 0");
}
} 1.2 全部子序列 of 一个字符串
题目描述:
打印一个字符串的全部子序列，注意包括空字符串
解法:
这类问题属于，子集类问题，每个元素都可能存在或不存在，复杂度属于2^N，非常高
通过分析，这个问题的递归树，每次选择，添加沿途字符或者不添加
在递归代码java中，注意String类的字符串，在添加一个字符串后，会自动new 一个新的String类
，因此递归过程中可以到最后返回子串，若果这里的容器是list等，要注意区分
public static List<String> allSubsets (String str) {
List<String> ans = new LinkedList<>();
if(str==null){
return ans;
}
if(str.length()==0){
ans.add("");
return ans;
}
// java 的string类变成 字符串数组，方便操作
char[] chs = str.toCharArray();
// 在子过程中，填充ans
String path = "";
process(chs, 0, path, ans);
return ans;
}
// 填写子过程
// str[0...index-1]的沿途决定，是path记录的
// str[index...] 每一个字符，都可以选择要或者不要
// 所有的子序列，都可以放到ans里面去
public static void process (char[] str, int index, String path, List<String> ans) {
if (index == str.length){
ans.add(path);
return;
}
// 添加沿途的字符
process(str, index+1, path, ans);
// 不添加沿途的字符, new path=path+String.valueOf(str[index])
process(str, index+1, path+String.valueOf(str[index]), ans);
} 1.3 子集
这个题属于1.2的扩展，非常类似，互为补充
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
解法一: 位运算
找到所有的子集，先保证集合按顺序排序, 每次选中和不选中元素，可以用位运算的0和1来模拟，因此从0到2^N-1遍历，每个数都看成二进制，比如000表示一个都不选，就是[]，001表示选中第一个元素,就是[a],以此类推。每个二进制上的1可以通过迭代移位来判断每个一。
用这个思路还可以解这道题:
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> output = new ArrayList<>();
for(int i=0; i < (1<<nums.length); i++){
// 处理每个数字, 比如0就是000, 1就是001
List<Integer> list = new ArrayList<>();
for(int j=0; j<nums.length; j++){
// 每次向右移动j位, 判断每个位上, 如果是1则添加对应的数
if( ((i>>j) & 1) == 1){
list.add(nums[j]);
}
}
output.add(list);
}
return output;
} 之后的解法可以参考图解
解法二: 动态规划
开始假设输出子集为空，每一步都向子集添加新的整数，并生成新的子集再合并到解集中。
- 解集初始化为空，遍历解集，给他新加子集[1] -> [ [],[1] ]
- 给解集中每个自己添加新的元素2，[]+2->[2], [1]+2->[1,2], 新解集位[ [],[1],[2],[1,2] ] 以此类推
public List<List<Integer>> subsets(int[] nums) {
// 初始化容器 和 边界情况
List<List<Integer>> output = new ArrayList<>();
output.add(new ArrayList<Integer>());
if(nums==null || nums.length==0){
return output;
}
// 大循环是: nums的每个数字
for(int elem : nums){
// 记录output的动态长度
int len = output.size();
// 依次给解集的每个元素加上elem成为新的元素，再加回到解集中
for(int i=0; i<len; i++){
// 创建一个list，不同引用，但和之前的内容一致
List<Integer> temp = new ArrayList<>(output.get(i));
temp.add(elem);
output.add(temp);
}
}
return output;
} 这里多插入一句，官方答案太难看懂了有一句非常晦涩，这里用了匿名内部类
参考资料1, 资料二
// 这项句话是，newSubsets 添加了一个 和curr的内容一样的ArrayList，
// 且它在被添加之前添加了num
newSubsets.add(new ArrayList<Integer>(curr){{add(num);}}); 解法三：递归树的遍历
模仿打印所有子序列的方法，在递归中，沿途决定加入nums[i]或者不加入，最后记录每个可能的路径
public List<List<Integer>> subsets(int[] nums) {
// 递归树
List<List<Integer>> output = new ArrayList<>();
// 递归序，记录所有路径
process(nums, 0, new ArrayList<Integer>(), output);
return output;
}
public static void process(int[] nums, int index, ArrayList<Integer> subset,List<List<Integer>> output) {
// base case: 到叶子结点了，记录每个选择路径
if(index == nums.length){
output.add(subset);
return;
}
// 每次给subset一个新引用，但要copy以前的内容，这就是一条新的路径，不干扰别的路径
// 不添加nums[i]
process(nums, index+1, new ArrayList<Integer>(subset), output);
// 添加nums[i]
process(nums, index+1, new ArrayList<Integer>(subset){{add(nums[index]);}}, output);
}
输入: [1,2,3]
输出: [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
和二叉树沿途路径一致 还可以有中序遍历, 分析递归树可以发现，按照中序遍历<left,root,right>，添加决策树上的路径，先是左，再中，再右，所以第一个加入的元素就是最左侧的3，然后是2，再是23，这些数都不是以1开头的，因为它们处于树的左侧，此时递归返回到index=0的节点，再从右侧遍历，所有以后的数都是以1开头的
public List<List<Integer>> subsets(int[] nums) {
// 递归树
List<List<Integer>> output = new ArrayList<>();
// 添加空集合
output.add(new ArrayList<Integer>());
// 树的前序遍历
inOrder(nums, 0, new ArrayList<Integer>(), output);
return output;
}
public static void inOrder(int[] nums, int index, ArrayList<Integer> subset,List<List<Integer>> output) {
// base case: 到叶子结点的子结点了，直接返回
if(index == nums.length){
return;
}
// 每次给新容器一个新引用，但要copy以前的内容
subset = new ArrayList<Integer>(subset);
inOrder(nums, index+1, subset, output);
// 打印时机
output.add(subset);
// 选择这个数 - index
subset.add(nums[index]);
inOrder(nums, index+1, subset, output);
}
输出: [[],[3],[2],[2,3], [1],[1,3],[1,2],[1,2,3]] 解法四: 回溯套路，暂时不会
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择 2.从暴力递归到动态规划
2.1 Fibonacci数列
图文解释参考dong哥
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
按上面的套路走，最后的结果就可以套这个框架：
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...) 千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。
1.暴力递归
// 暴力递归，时间复杂度指数级别, O(2ˆN), 展开递归树就可以得到
public static int fib_1(int N){
if(N == 1 || N == 2){
return 1;
}
return fib_1(N-1) + fib_1(N-2);
} 
dong哥和左神都推荐，但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。
这个递归树怎么理解？就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。
递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。
首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸。
2.傻缓存的递归解法
即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。
啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。
啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
// 记忆化搜索，把递归树中重复的计算，有一个map记录下来记录下来
public static int fib_2(int N){
int [] map = new int[N+1];
return fib_2_helper(map, N);
}
public static int fib_2_helper(int[] map, int N){
if(N == 1 || N == 2){
return 1;
}
if (map[N] != 0){
return map[N];
}else { // 没有出现过，递归计算
map[N] = fib_2_helper(map, N-1) + fib_2_helper(map, N-2);
}
return map[N];
} 3.dp 数组的迭代解法
有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算岂不美哉！
// 记忆化搜索改成dp table，效率基本一致
public static int fib_3(int N){
// 可变参数: N[1~N]
int[] dp = new int[N+1];
// base case: dp[0] 空着不作处理
dp[1] = dp[2] = 1;
// generai case
for(int i=3; i<N+1; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[N];
} 4.空间压缩的DP
根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)。
这个技巧就是所谓的「状态压缩」，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，上述例子就相当于把DP table 的大小从 n 缩小到 2。后续的动态规划章节中我们还会看到这样的例子，一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从 O(n^2) 压缩到 O(n)。
// 空间压缩的DP table
public static int fib_4(int N){
if(N == 1 || N == 2){
return 1;
}
int pre = 1;
int cur = 1;
int sum = 0;
for(int i=3; i<=N; i++){
sum = pre + cur;
pre = cur;
cur = sum;
}
return sum;
} 
京公网安备 11010502036488号