从暴力递归到动态规划

动态规划没有那么难，但是很多老师在讲课的过程中讲的并不好，由此写下一篇文章记录学习过程

1.题目链接：LeetCode518

从暴力递归开始

暴力递归就是尝试，这道题比较简单，从coins[0]开始尝试，coins[0]选0个，那么用剩下的coins[1...n]凑出amount的数量为a；coins[0]选1个，那么用剩下的coins[1...n]凑出amount-coins[0]的数量为b；coins[0]选2个，那么用剩下的coins[1...n]凑出amount-coins[0]*2的数量为c......依次继续下去，a+b+c+...的结果就为最终答案

public static int coins1(int[] coins,int amount) {
    if(coins == null || coins.length == 0)
        if(amount == 0)
            return 1;
        else 
            return 0;
    return process1(coins,0,amount);
}
    
//index:可以自由使用index及其之后所有的钱
//amount：目标钱数
public static int process1(int[] coins,int index,int amount) {
    int res = 0;
    if(amount == 0)
        return 1;
    if(amount != 0 && index >= coins.length)
        return 0;
    else
        for(int num = 0;coins[index] * num <= amount;num++)
            res += process1(coins,index + 1,amount - coins[index] * num);
    return res;
}

初级优化

考虑这么一个问题，假设可选的钱数有200,100,50,10，目标钱数是1000，选了0张200,4张100，或者选了1张200,2张100，这两种情况剩下的目标i都是index = 2,amount = 600。只要index和amount确定，后面的值一定都是一样的，会产生很多重复的递归过程，所以第一个优化版本就有了，用一个map保存所有记录，当遇到同样过程的时候就直接调用

//key:"index_aim"
//value:返回值
public static HashMap<String,Integer> map = new HashMap<>();
    
public static int coins1(int[] coins,int amount) {
    if(coins == null || coins.length == 0)
        if(amount == 0)
            return 1;
        else 
            return 0;
    return process1(coins,0,amount);
}
    
//index:可以自由使用index及其之后所有的钱
//amount：目标钱数
public static int process1(int[] coins,int index,int amount) {
    int res = 0;
    if(amount == 0)
        return 1;
    if(amount != 0 && index >= coins.length)
        return 0;
    else
        for(int num = 0;coins[index] * num <= amount;num++) {
            String key = String.valueOf(index+1) + "_" + String.valueOf(amount - coins[index] * num);
            if(map.containsKey(key))
                res += map.get(key);
            else
                res += process1(coins,index + 1,amount - coins[index] * num);
        }
    map.put(String.valueOf(index+1) + "_" + String.valueOf(amount - coins[index] * amount), res);
    return res;
}

高级优化

构建一张二维表（N=coins.length），画红色叉的部分就是最终需要的答案，有一些值可以直接根据边界条件直接写出，就先写在表中，然后我们观察一个一般位置(index,amount)，根据递归式可知，二维表中(index,amount)位置的值是(index+1,amount)+(index+1,amount-coins[index])+...的值，因此从倒数第二排以直网上填满整张表，最终答案也就出来了，中间没有任何重复算的部分

举个例子，假设amount=5，coins[]={1,2,5}，画出来的表如下，蓝色部分表示根据边界条件直接写的值，黑色部分表示推导的值，红色部分表示最终要求的结果

public static int coins1(int[] coins,int amount) {
    if(coins == null || coins.length == 0)
        if(amount == 0)
            return 1;
        else 
            return 0;
    return process1(coins,0,amount);
}
    
public static int process1(int[] coins,int index,int amount) {
    int n = coins.length;
    int[][] dp = new int[n + 1][amount+1];
    //首先将能填的都填上
    for(int i = 0;i <= n;i++)
        dp[i][0] = 1;
    for(int i = 1;i <= amount;i++)
        dp[n][i] = 0;
    
    //开始循环填表
    for(int i = n - 1;i >= 0;i--) {//行
        for(int j = 1;j <= amount;j++) {//列
            for(int k = j;k >= 0;k -= coins[i])
                dp[i][j] += dp[i + 1][k];
        }
    }
    return dp[0][amount];
}

最终优化

假设我们现在正在算$dp[i][j]，dp[i][j]=dp[i+1][j]+dp[i+1][j-conins[i]]+...$；又因为$dp[i][j-coins[i]]=dp[i+1][j-coins[i]\times2]+dp[i+1][j-coins[i]\times3]$，所以$dp[i][j]=dp[i+1][j]+dp[i][j-coins[i]]$

class Solution {
    public static HashMap<String,Integer> map = new HashMap<>();
    public int change(int amount, int[] coins) {
        map.clear();
        if(coins == null || coins.length == 0) {
            if(amount == 0)
                return 1;
            else 
                return 0;
        }
        return process1(coins,0,amount);
    }
    public static int process1(int[] coins,int index,int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount+1];
        //首先将能填的都填上
        for(int i = 0;i <= n;i++)
            dp[i][0] = 1;
        
        //开始循环填表
        for(int i = n - 1;i >= 0;i--) {//行
            for(int j = 1;j <= amount;j++) {//列
                dp[i][j] = dp[i + 1][j];
                dp[i][j] += (j - coins[i]) >= 0 ? dp[i][j-coins[i]] : 0;
            }
        }
        return dp[0][amount];
    }
}

2.题目链接：LeetCode486

从暴力递归开始

对于这个问题，我们假设先选的人最终得到分数的函数是int f(int[] arr,int i,int j)，i表示最左边的下标，j表示最右边的下标，对于先选的人来说，边界条件就是当i=j时，返回arr[i]；对于后选的人来说，最终得到分数的函数是int s(int[] arr,int i,int j)，同样的，边界条件是i=j时，返回0

如果不是边界条件，先选的人得到的分数递归式就应该是：i位置拿走然后加上s(arr,i+1,j)和j位置拿走然后加上s(arr,i,j-1)两者中较大的那个；对于后选的那个来说拿走的肯定是f(arr,i+1,j)和f(arr,i,j-1)中较小的那个，因此暴力递归版本的代码就出来了

class Solution {
    public boolean PredictTheWinner(int[] arr) {
        if(arr == null || arr.length == 0)
            return true;
        if(f(arr,0,arr.length - 1) >= s(arr,0,arr.length - 1) || arr.length == 1)
            return true;
        return false;
    }
    public static int f(int[] arr,int i,int j) {
        if(i == j)
            return arr[i];
        return Math.max(arr[i] + s(arr,i + 1,j),arr[j] + s(arr,i,j-1));
    }
    
    public static int s(int[] arr,int i,int j) {
        if(i == j)
            return 0;
        return Math.min(f(arr,i + 1,j),f(arr,i,j - 1));
    }
}

动态规划

这道题不是很一样，因为一个函数的值需要另一个函数来确定，两个函数是相互影响的，因此需要两张表分别存，下图蓝色部分是因为边界条件可以直接填的，黑色部分按照顺序进行填写，红色部分是最终答案。解释一下，因为i不可能大于j，i==j的时候就返回了，因此i大于j的部分全部都不用填

3.某里笔试题

现有一条坐标轴，一个机器人初始停留在m位置,可以走p步,如果在n位置只能往左走,如果在1位置只能往右走，问最终停留在k上有多少种情况

从暴力递归开始

特殊情况单独进行递归即可

//n：一共有n个位置
//m：初始停留的位置
//p：可以走的步数
//k：最终停留的位置
public static int ways(int n,int m,int p,int k) {
    if(n < 2 || m < 1 || m > n || p < 0 || k < 1 || k > n)
        return 0;
    if(p == 0)
        return m == k ? 1 : 0;
    int res = 0;
    if(m == 1)
        res += ways(n,m + 1,p - 1,k);
    else if(m == n)
        res += ways(n,m - 1,p - 1,k);
    else
        res += ways(n,m + 1,p - 1,k) + ways(n,m - 1,p - 1,k);
    return res;
}

动态规划

见下图，类似一个杨辉三角

//n：一共有n个位置
//m：初始停留的位置
//p：可以走的步数
//k：最终停留的位置
public static int ways(int n,int m,int p,int k) {
    int[][] dp = new int[p + 1][n + 1];
    dp[0][k] = 1;
    for(int i = 1;i <= p;i++) {//行，p
        for(int j = 1;j <= n;j++) {//列， n
            if(j == 1)
                dp[i][j] = dp[i - 1][j + 1];
            if(j == n)
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
        }
    }
    return dp[p][m];
}

4.题目链接：LeetCode10

从暴力递归开始

假设有一个函数 boolean f(int i,int j)，含义是s字符串从i开始往后的字符能否和p字符串从j位置开始往后匹配成功，返回值是boolean，分三种情况

• j < p.length - 1 && p[j+1] != '*'

在这种情况下只有当(p[j] = s[i] || p[j] = '.')时才能继续匹配f(i+1,j+1)，否则直接返回false

• j < p.length - 1 && p[j+1] == '*'

这种情况有特别多分支，假设s串为"aaaab"，p串为"c×某某某",此时就需要c×配合，将c变为0个，然后判断f(i,j+2)能否匹配；假设s串为"aaab"，p串为"a×某某某"，此时就需要枚举a×变成几个a，假设变成0个a，那就要判断f(i,j+2)能否匹配，假设变成1个a，那就需要判断f(i+1,j+2)能否匹配，假设变成2个a，那就要判断f(i+2,j+2)能否匹配，以直往下....

class Solution {
    static char[] str,exp;
    public boolean isMatch(String s, String p) {
        str = s.toCharArray();
        exp = p.toCharArray();
        return process(0,0);
    }
    public static boolean process(int i,int j) {
        if(j == exp.length)
            return i == str.length;
        if(j + 1 == exp.length || exp[j + 1] != '*') 
            return i != str.length && (exp[j] == str[i] || exp[j] == '.') 
            && process(i + 1,j + 1);
        //exp的j+1位置不仅有字符，并且exp[j] == '*'
        while(i != str.length && (exp[j] == str[i] || exp[j] == '.')) {
            if(process(i,j+2)) 
                return true;
            i++;
        }
        return process(i,j+2);
    }
}

动态规划

先把最后两列和最后一行填满，然后依次填即可

class Solution {
    static char[] str,exp;
    public boolean isMatch(String str, String exp) {
        if(str == null || exp == null)
        return false;
        char[] s = str.toCharArray();
        char[] e = exp.toCharArray();
        boolean[][] dp = initDpMap(s,e);
        for(int i = s.length - 1; i > -1 ;i--) {
            for(int j = e.length - 2;j > -1;j--) {
                if(e[j + 1] != '*')
                    dp[i][j] = (s[i] == e[j] || e[j] == '.') && dp[i + 1][j + 1];
                else {
                    int si = i;
                    while(si != s.length && (s[si] == e[j] || e[j] == '.')) {
                        if(dp[si][j + 2]) {
                            dp[i][j] = true;
                            break;
                        }
                        si++;
                    }
                    if(dp[i][j] != true)
                        dp[i][j] = dp[si][j + 2];
                }
            }
        }
        return dp[0][0];
    }
    public static boolean[][] initDpMap(char[] s,char[] e) {
        int slen = s.length;
        int elen = e.length;
        boolean[][] dp = new boolean[slen + 1][elen + 1];
        dp[slen][elen] = true;
        for(int i = elen - 2;i > -1;i -= 2) {
            if(e[i] != '*' && e[i + 1] == '*')
                dp[slen][i] = true;
            else
                break;
        }
        if(slen > 0 && elen > 0) 
            if((e[elen - 1] == '.' || s[slen - 1] == e[elen - 1])) 
                dp[slen - 1][elen - 1] = true;
        return dp;
    }
}