方法1：递归（Recursion）
递归是一极其常用的技巧。在我们的实际生产中也会经常用到，比如树遍历（地址，类目之类的）。
递归由两个过程组成，即将原问题一点点分解为基本子问题的的"递"过程，和通过基本子问题的解一步步向上得到原问题的解的"归"过程。
原问题 ↓
/ \ 递
子问题 子问题 ↓
/ \ / \
子问题 .............. ↑
..... 归
基本子问题 基本子问题 ↑这里的基本子问题表示已经无法分解的问题，这样的问题的答案通常的显而易见的。
思想
递归需要满足的三个条件
- 一个问题可以分解为一个或者多个子问题的解。
- 子问题除了问题规模比原问题小，其求解思路是和原问题是一样的。
- 存在终止条件。
通过将问题分解成规模更小的子问题，一步步到达基本子问题，再由基本子问题的解一步步归纳得出原问题的解。
由于原问题与子问题的求解思路是一样的，通常我们可以写出他们的递推公式，形如f(n) = g(f(n-1))。n-x或者n/x都是必然的，因为原问题要一步步分解。
但是问题不能一直分解下去，必然会到达基本子问题，比如f(1) f(2)是确定的，这就这就意味着递归不是无限的是有终止条件的。其实这也隐含了问题是有解的。
我们需要注意优化三个问题
- 明确终止条件，通常该条件会在最开始就判断。
- 小心栈溢出。递归的本质是将问题摊开来处理，在问题规模过大的或者分解子问题降低的数量级国小的时候会发生栈溢出，毕竟方法栈的深度是有限的。没有明确终止条件通常也会导致栈溢出。
- 裁剪掉重复的计算。将问题摊开处理通常会有大量的重复的子问题，这些子问题在求解之后应该为缓存起来待下一次相同的子问题使用。可以节省大量的计算时间。
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
所有的递归都可以变成循环。循环通常有更加优良的性能，但是可能不会向递归一样直观。
力扣70：爬楼梯问题
问题描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的走法可以爬到楼顶呢？首先当楼梯只有1阶的时候，我们只有走一台阶这一种走法。
而当楼梯有2阶的时候，我们可以走两次一台阶或者走一次两个台阶这两种走法。
而当楼梯有3阶的时候，我们有两种选择，走一个台阶或者走两个台阶。
如果走一个台阶，那么还剩下两个台阶要走，那么走法和有两个台阶的走法是一样的；如果是走两个台阶，那么还剩下一个台阶要走，那么走法和有一个台阶的走法是一样的。
那么3阶的走法就等于走2阶的走法加上走1阶的走法。也就是有三种走法。
那么当楼梯有4阶的时候，我们依然有两种选择，走一个台阶或者走两个台阶。
如果走一个台阶，那么我们还剩下三个台阶要走，走法和有三阶楼梯的走法是一样的；如果走两个台阶，那么我们还剩下2个台阶要走，走法和有两阶楼梯的走法是一样的。
那么4阶的走法就等于3阶的走法假设走2阶的走法。
同理我们可以推导出，n阶楼梯的走法f(n) = f(n-1) + f(n-2)。其中有两个特殊情况，一是当楼梯台阶n=1的时候，只有一种走法，当楼梯台阶n=2的时候，有两种走法。
f(1) = 1;
f(2) = 2;
f(n) = f(n-1) + f(n-2);代码：
package cn.lishiyuan.leetcode;
/**
* 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
*
* 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
*
* * * 示例 1：
*
* 输入：n = 2
* 输出：2
* 解释：有两种方法可以爬到楼顶。
* 1. 1 阶 + 1 阶
* 2. 2 阶
* 示例 2：
*
* 输入：n = 3
* 输出：3
* 解释：有三种方法可以爬到楼顶。
* 1. 1 阶 + 1 阶 + 1 阶
* 2. 1 阶 + 2 阶
* 3. 2 阶 + 1 阶
*
*/
public class LeetCode70 {
/**
* 递归解法
* @return
*/
public int recursion(int n){
if(n<1){
return 0;
}
// 只有一个台阶的时候只有一种解法
if(n==1) return 1;
// 只有两个台阶的有两种解法（走一次两个台阶、走两次一个台阶）
if(n==2) return 2;
// 走n个台阶有两种走法，走一步和走两步。所以n阶的走法就是走n-1台阶和走n-2台阶的和。
return recursion(n-1)+recursion(n-2);
}
/**
* 改循环
* @return
*/
public int recursionToFor(int n){
if(n<1){
return 0;
}
// 只有一个台阶的时候只有一种解法
if(n==1) return 1;
// 只有两个台阶的有两种解法（走一次两个台阶、走两次一个台阶）
if(n==2) return 2;
// n-1台阶的走法
int oneStep=2;
// n-2台阶的走法
int twoStep=1;
int nowStep=0;
for(int i=3;i<=n;i++){
nowStep = oneStep + twoStep;
twoStep = oneStep;
oneStep = nowStep;
}
// 走法
return nowStep;
}
/**
* 递归解法优化，添加缓存，优化分支
* @return
*/
public int recursionPro(int n,int[] cache){
if(n<1){
return 0;
}
// 只有一个台阶的时候只有一种解法
if(n==1) return 1;
// 只有两个台阶的有两种解法（走一次两个台阶、走两次一个台阶）
if(n==2) return 2;
if(cache[n-1] > 0) return cache[n-1];
cache[n-1] = recursionPro(n-1,cache)+recursionPro(n-2,cache);
return cache[n-1];
}
}这里提供了三种解法：
递归解法
纯递归解法效率并不高，一方面大量的递归调用方法本质上是将问题展开求解，本身是一个耗时耗内存的操作，另一方面有大量的重复计算耗费了时间。
递归树展开
对于 recursion(n)，每次调用会分裂为两个子问题：
recursion(n-1)recursion(n-2)
以 n=5 为例，递归树如下：
f(5)
/ \
f(4) f(3)
/ \ / \
f(3) f(2) f(2) f(1)
/ \
f(2) f(1)递归调用次数：约为 O(2^n)（指数级增长），时间复杂度为 O(2^n) （实际上是斐波那契数列，O(φⁿ) 约为 O(1.618ⁿ) ，φ是黄金分割比）
由于需要额外的栈空间，空间与n线性相关，空间复杂度是（O(n)）
循环解法
将循环改写为递归可以大大的提高效率，一方面不需要大量的递归方法栈调用，节省了内存空间，另一方面没有大量的重复计算，极大的提高了计算效率。但是不能直观的表示我们的递推公式。
稳定解法，空间复杂度O(1)，时间复杂度O(n)，无栈溢出风险。
记忆化递归 （动态规划）
将已求解的台阶放入缓存，其他分支计算到相同阶数的时候直接取出结果可以大大提高计算效率。
时间复杂度O(n)，空间复杂度O(n)（因为需要缓存和额外的栈空间）
汉诺塔问题
问题描述
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。设有三个柱子A，B，C，目标是将A柱子种所有的圆盘移动到C柱子。
首先，当A柱子只有一个圆盘的时候，可以直接将圆盘从A移动到C。
如果有两个圆盘，则需要将顶部圆盘从A移动到B，再将底部圆盘从A移动到C，再将顶部圆盘从B移动到C。
如果有三个圆盘，那么底部圆盘，从A移动到C需要先将顶部两个圆盘移动到B，也就是说，对于顶部两个圆盘来说，他们的目标是B，也就是说首先得先将A柱子顶部的两个圆盘移动到B柱子之上，在完成底部圆盘从A移动到C之后，目标变成了将B柱子的两个圆盘移动到C柱子之上。
那么对于n个圆盘来说，它包含三个步骤，将n-1个圆盘从A移动到B，将底部圆盘从A移动到C，再将n-1个圆盘从B移动到C。
也就是说，1. 圆盘移动的目标是变化的，2.移动n和圆盘的前提是将n-1个圆盘移动到中间柱子。
那么我们可以得出
A(1) → C = A → C
A(n) → C = A(n-1) → B , A → C , B(n-1) → C递归解法
这里使用到了线性表2：栈和队列里面实现的栈
package cn.lishiyuan.leetcode;
import cn.lishiyuan.algorithm.stack.LeeStack;
/**
* 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
* (1) 每次只能移动一个盘子;
* (2) 盘子只能从柱子顶端滑出移到下一根柱子;
* (3) 盘子只能叠在比它大的盘子上。
*
* 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
*
* 你需要原地修改栈。
*
* 示例 1：
*
* 输入：A = [2, 1, 0], B = [], C = []
* 输出：C = [2, 1, 0]
* 示例 2：
*
* 输入：A = [1, 0], B = [], C = []
* 输出：C = [1, 0]
*/public class TowerOfHanoi {
public void move(LeeStack<Integer> start,int startSize, LeeStack<Integer> temp , LeeStack<Integer> target){
if(startSize == 1){
Integer peek = start.peek();
target.push(start.pop());
System.out.println("将元素"+ peek +"从"+start+"移动到"+target);
return;
}
startSize = startSize - 1;
// 先将N-1个元素从start移动到temp
move(start, startSize , target,temp);
// 移动完成后将底部元素从start移动到target
Integer peek = start.peek();
target.push(start.pop());
System.out.println("将元素"+ peek +"从"+start+"移动到"+target);
// 再将N-1个元素从temp移动到target
move(temp, startSize , start, target);
}
}
评论已关闭