从暴力递归到动态规划（一）

2020-12-11

整理一篇和递归、动态规划有关的文章

暴力递归

暴力递归就是尝试
不记录子问题的解

问题一：汉诺塔问题

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。打印最优轨迹。
解法：N-1先腾路，再把最后一片移过去
- ①先把左边的(1~N-1)移动到中间
- ②把第N片移动到右柱
- ③把中间的(1~N-1)移动到右柱

代码：

public static void func(int N,String from,String to,String other){
	if(N==1)
	    System.out.println("move 1 from "+from+" to "+to);
	else {
	    func(N-1,from,other,to);
	    System.out.println("move "+N+" from "+from+" to "+to);
	    func(N-1,other,to,from);
	}
}

附：移动步数一定是2^N-1步——T(N)=2*T(N-1)+1，根据公式即可证明，这里不再赘述

问题二：给定一个栈，请你逆序这个栈（只用递归函数，不能申请额外空间）

首先实现这样一个釜底抽薪的方法：该方法能把一个栈底元素抽出，其余部分没有变化，返回栈底元素

public static int f(Stack<Integer> s) {
    int top=s.pop();//顶部元素
    if(s.isEmpty())
        return top;
    int ret=f(s);
    s.push(top);
    return ret;
}

实现方法

public static void reverse(Stack<Integer> s) {
    if(s.isEmpty())
        return;
    int bottom=f(s);
    reverse(s);
    s.push(bottom);
}

问题三：生成一个字符串所有子序列

子串和子序列：子串指连续的某一段字符串子集，子序列指相对次序相同的，字符串的某一段子集（不一定要连续）

同leetcode.78子集思路一致，用递归回溯解决

子集代码如下：

class Solution {
    List<List<Integer>> ret=new ArrayList<>();
    List<Integer> ans=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int i){
        // if(i==nums.length){
        //     ret.add(new ArrayList<>(ans));
        //     return;
        // }
        // ans.add(nums[i]);
        // dfs(nums,i+1);
        // ans.remove(ans.size()-1);
        // dfs(nums,i+1);
        ret.add(new ArrayList<>(ans));
        for(int j=i;j<nums.length;j++){
            ans.add(nums[j]);
            dfs(nums,j+1);
            ans.remove(ans.size()-1);
        }
    }
}

子序列代码如下：

public static List<String> subs(String s){
    char[] str=s.toCharArray();
    List<String> ret=new ArrayList<>();
    String path="";
    f(str,0,path,ret);
    return ret;
}
private static void f(char[] str,int i,String path,List<String> ret) {
    if(i==s.length()) {
        ret.add(path);
        return;
    }
    String tmp=path+s[i];
    f(s,i+1,tmp,ret);
    f(s,i+1,path,ret);
}

问题四：求字符串全排列（剑指offer27.字符串的排列）

类似leetcode.46全排列、47.全排列Ⅱ

class Solution {
    public ArrayList<String> Permutation(String str) {
        char[] s=str.toCharArray();
        Set<String> ret=new TreeSet<>();//去重
        perm(s,ret,0);
        return new ArrayList<>(ret);
    }
    //str[0……i-1]已做好决定
    //str[i……]依次移到i位置（包括str[i]）
    public void perm(char[] s,Set<String> ans,int i){
        if(i==s.length-1){
            ans.add(String.valueOf(s));
            return;
        }
        for(int j=i;j<s.length;j++){
            swap(s,i,j);
            perm(s,ans,i+1);
            swap(s,i,j);
        }
    }
    public void swap(char[] s,int i,int j){
        char tmp=s[i];
        s[i]=s[j];
        s[j]=tmp;
    }
}

最优方法：分支限界

class Solution {
    public ArrayList<String> Permutation(String str) {
        char[] s=str.toCharArray();
        ArrayList<String> ret=new ArrayList<>();
        perm(s,ret,0);
        return ret;
    }
    public void perm(char[] s,ArrayList<String> ans,int i){
        if(i==s.length-1){
            ans.add(String.valueOf(s));
            return;
        }
        boolean[] used=new boolean[26];//表示已经访问过，类似哈希表
        for(int j=i;j<s.length;j++){
            if(!used[s[j]-'a']){
                used[s[j]-'a']=true;
                swap(s,i,j);
                perm(s,ans,i+1);
                swap(s,i,j);
            }
        }
    }
    public void swap(char[] s,int i,int j){
        char tmp=s[i];
        s[i]=s[j];
        s[j]=tmp;
    }
}

从左往右尝试模型1

规定1和A对应，2和B对应……给定一个只有数字组成的字符串，返回有多少种转化结果

public static int number(String s) {
    if(s==null||s.length()==0)
        return 0;
    return f(s.toCharArray(),0);
}
public static int f(char[] s,int i) {
    if(i==s.length)//终止位置
        return 1;
    if(i>s.length||s[i]=='0')//走不通
        return 0;
    if(s[i]=='1')
        return f(s,i+1)+f(s,i+2);
    if(s[i]=='2') {
        if(i<s.length-1&&s[i+1]>='0'&&s[i+1]<='6')
            return f(s,i+1)+f(s,i+2);
    }
    return f(s,i+1);
}

从左往右尝试模型2

背包问题：给定两个长度都为N的数组weights和values，分别表示第i号物品重量和价值，给一个正数bag，表示载重bag的袋子，你装的物品不能超过这个袋子，求装下的最大价值

public static int getmaxValue(int[] w,int[] v,int bag) {
    return f(w,v,0,bag);
}
//从index开始的剩余空间，f表示从index开始返回的价值
public static int f(int[] w,int[] v,int index,int rest) {
    if(index==w.length||rest<=0)//无论如何都不可能获得价值
        return 0;
    int p1=f(w,v,index+1,rest);
    int p2=Integer.MIN_VALUE;
    if(w[index]<=rest)
        p2=f(w,v,index+1,rest-w[index])+v[index];
    return Math.max(p1, p2);
}

范围尝试模型

给定一数组arr，表示不同数值纸牌排成一排，理行人玩家A和B依次拿走每张牌，每次只能拿走两边的牌。玩家A先拿，B后拿。问最后获胜者分数。

public class Solution{
    public static int win(int[] arr) {
		if(arr==null||arr.length==0)
			return 0;
		return Math.max(f(arr,0,arr.length-1),s(arr,0,arr.length-1));
	}
	//该函数表示在一个纸牌中先拿能拿到的最多分数
	public static int f(int[] arr,int l,int r) {
		if(l==r)
			return arr[l];
		int left=arr[l]+s(arr,l+1,r);
		int right=arr[r]+s(arr,l,r-1);
		return Math.max(left, right);
	}
	//该函数表示在一个纸牌中后拿能拿到的最多分数
	public static int s(int[] arr,int l,int r) {
		if(l==r)
			return 0;
		return Math.min(f(arr,l+1,r), f(arr,l,r-1));
	}
}