java 递归和动态规划

Myth丶恋晨 2022-06-13 00:14 202阅读 0赞

# 1、斐波那契系类问题的递归和动态规划 #

## 1.1 O(N)的解法 ##

按照1，1，2，3，5.。。的顺序，依次求解即可。

package DynamicProgramming;
    
    public class FibonacciSequenceV1 {
    
        public static int getN(int n){
            if(n<0)
                return 0;
            if(n==1 || n==2)
                return 1;
            int res = 1;
            int pre = 1;
            int temp = 0;
            for(int i =3 ;i<=n;i++){
                temp = res;
                res = pre + res;
                pre = temp;
            }
            return res;
        }
    
        public static void main(String[] args){
            System.out.println(getN(10));
        }
    }

## O(logN)的解法 ##

主要用到了矩阵的思想，看下面的递推公式：

![Image 1][]

package DynamicProgramming;
    
    public class FibonacciSequenceV2 {
    
        public static int[][] matrixPower(int[][] matrix,int p){
            int[][] res = new int[matrix.length][matrix[0].length];
            for(int i=0;i<matrix.length;i++){
                res[i][i] = 1;
            }
            int[][] temp = matrix;
            for(;p !=0; p >>= 1){
                if((p & 1) == 1){
                    res = multiMatrix(res,temp);
                }
                temp = multiMatrix(temp,temp);
            }
            return res;
        }
    
        public static int[][] multiMatrix(int[][] m1,int[][] m2){
            int[][] res = new int[m1.length][m1[0].length];
            for(int i=0;i<m1[0].length;i++){
                for(int j=0;j<m1.length;j++){
                    for(int k=0;k<m2.length;k++) {
                        res[i][j] += (m1[i][k] * m2[k][j]);
                    }
                }
            }
            return res;
        }
    
        public static int getN(int n){
            if(n<1)
                return 0;
            if(n==1 || n==2)
                return 1;
            int[][] matrix = {
       {1,1},{1,0}};
            int[][] res = matrixPower(matrix,n-2);
            return res[0][0] + res[1][0];
        }
    
        public static void main(String[] args){
            System.out.println(getN(10));
        }
    
    }

# 2、矩阵的最短路径和 #

![Image 1][]

使用动态规划的方法，建立dp数组，dp\[i\]\[j\]代表从(0,0）位置到该处的最短路径。当然，我们可以使用空间压缩的方法，只用一维数组，保存每一行的结果，这样有效的降低的空间复杂度。

package DynamicProgramming;
    
    public class minPathSum {
    
        public static int getMinPath(int[][] distance){
            int[] res = new int[distance[0].length];
            for(int i=0;i<distance.length;i++){
                for(int j=0;j<distance[0].length;j++){
                    if(i==0 && j==0)
                        res[j] = distance[0][0];
                    else if(i==0)
                        res[j] = distance[i][j] + res[j-1];
                    else if(j==0)
                        res[j] = distance[i][j] + res[j];
                    else
                        res[j] = Math.min(res[j],res[j-1]) + distance[i][j];
                }
            }
            return res[distance[0].length-1];
        }
        public static void main(String[] args){
            int[][] distance = {
                    {1,3,5,9},
                    {8,1,3,4},
                    {5,0,6,1},
                    {8,8,4,0}};
            System.out.println(getMinPath(distance));
        }
    }

# 3、换钱最少的货币数 #

## 3.1 每种货币数量无限 ##

![Image 1][]

在每种货币数量无限的情况下，使用动态规划的方法，从二维数组的角度出发，dp\[i\]\[j\]代表使用arr\[0,1..i\]货币的情况下，组成j所需的最小张数。后面使用空间压缩的方法，可以将二维数组变为一维数组。

值得注意的地方是，我们首先给一维数组全部赋值了max，而不是使用默认值0，max表示无法组成目标货币，0表示的是最少用0张就可以组成目标货币，这显然是不合理的。

package DynamicProgramming;
    
    public class minCoins {
        public static int getMinCoins(int[] arr,int aim){
            if(arr == null || arr.length == 0 || aim < 0)
                return -1;
            int[] res = new int[aim+1];
            int max = Integer.MAX_VALUE;
            for(int i=1;i<=aim;i++){
                res[i] = max;
            }
            int leftup;
            for(int i=0;i<arr.length;i++){
                for(int j=0;j<=aim;j++){
                    if(i==0)
                        if(j>0 && j % arr[i] == 0)
                            res[j] = j / arr[i];
                    else{
                        leftup = max;
                        if(j >= arr[i] && res[j-arr[i]] != max)
                            leftup = res[j-arr[i]] + 1;
    
                         res[j] = Math.min(leftup,res[j]);
                    }
                }
            }
            return res[aim] != max?res[aim]:-1;
        }
    
        public static void main(String[] args){
            int[] arr = {5,2,3};
            int aim = 20;
            System.out.println(getMinCoins(arr,aim));
        }
    }

## 3.2 每种货币只能使用1张 ##

![Image 1][]

思路跟上面的题目是一样的，不过需要注意的一点是，由于每张货币只能使用一次，因此我们在内部遍历每一行时，需要从后往前遍历。因为如果从前往后遍历，会出现硬币被多次使用的情况。

package DynamicProgramming;
    
    public class minCoinsV2 {
        public static int getMinCoins(int[] arr,int aim){
            if(arr == null || arr.length == 0 || aim < 0)
                return -1;
            int[] res = new int[aim+1];
            int max = Integer.MAX_VALUE;
            for(int i=1;i<=aim;i++){
                res[i] = max;
            }
            if(arr[0] <= aim)
                res[arr[0]] = 1;
            int leftup;
            for(int i=1;i<arr.length;i++){
                for(int j=aim;j>0;j--){
                    leftup = max;
                    if(j >= arr[i] && res[j-arr[i]] != max)
                        leftup = res[j-arr[i]] + 1;
                    res[j] = Math.min(leftup,res[j]);
                }
            }
            return res[aim] != max?res[aim]:-1;
        }
    
        public static void main(String[] args){
            int[] arr = {5,2,3};
            int aim = 20;
            System.out.println(getMinCoins(arr,aim));
        }
    }

# 4、换钱的方法数 #

![Image 1][]

这里要注意的一点是，组成0元的方法是1种，而不是0种。

package DynamicProgramming;
    
    public class MaxChangeCoinsMethod {
        public static int getMaxCoinsMethod(int[] arr,int aim){
            if(arr == null || arr.length == 0 || aim < 0)
                return 0;
            int[] res = new int[aim+1];
            for(int j=0;j * arr[0] <= aim ;j++){
                res[j * arr[0]] = 1;
            }
            for(int i=1;i<arr.length;i++){
                for(int j=1;j<=aim;j++){
                    if(j >= arr[I])
                        res[j] += (res[j-arr[i]]);
                }
            }
            return res[aim];
        }
        public static void main(String[] args){
            int[] arr = {5,10,25,1};
            int aim = 15;
            System.out.println(getMaxCoinsMethod(arr,aim));
        }
    }

# 5、最长递增子序列 #

![Image 1][]

package DynamicProgramming;
    
    public class LongestIncreaseList {
    
        public static int[] getLongestIncreaseList(int[] arr){
            int[] ends = new int[arr.length];
            ends[0] = arr[0];
            int[] dp = new int[arr.length]; //以index对应的数结尾的时候，最大递增子序列的长度
            int right = 0;
            int l = 0;
            int r = 0;
            int m = 0;
            for(int i=1;i<arr.length;i++){
                l = 0;
                r = right;
                while(l<=r){
                    m = (r-l) / 2 + l;
                    if(ends[m]<=arr[I])
                        l = m + 1;
                    else
                        r = m - 1;
                }
                right = Math.max(l,right);
                ends[l] = arr[I];
                dp[i] = l + 1;
            }
    
            return dp;
        }
    
        public static int[] generateLIS(int[] arr,int[] dp){
            int len = 0;
            int index = 0;
            for(int i=0;i<dp.length;i++){
                if(dp[i] > len){
                    len = dp[i];
                    index = I;
                }
            }
            int[] lis = new int[len];
            lis[--len] = arr[index];
            for(int i=index;i>=0;i--){
                if(arr[i] < arr[index] && dp[i] == dp[index] - 1){
                    lis[--len] = arr[i];
                    index = I;
                }
            }
            return lis;
        }
    
        public static void main(String[] args){
            int[] arr = {2,1,5,3,6,4,8,9,7};
            int[] dp = getLongestIncreaseList(arr);
            int[] res = generateLIS(arr,dp);
            for(int i=0;i<res.length;i++)
                System.out.println(res[I]);
        }
    }

# 6、最长公共子序列问题 #

![Image 1][]

package DynamicProgramming;
    
    public class LongestCommonSubStr {
    
        public static int[][] findLongestSubStrDP(String str1,String str2){
            char[] char1 = str1.toCharArray();
            char[] char2 = str2.toCharArray();
            int[][] dp = new int[char1.length][char2.length];
            for(int i=0;i<char1.length;i++){
                for(int j=0;j<char2.length;j++){
                    if(i==0){
                        dp[i][j] = (char2[j] == char1[i] ? 1:0);
                    }
                    else if(j==0){
                        dp[i][j] = (char2[j] == char1[i] ? 1:0);
                    }
                    else{
                        dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                        if(char1[i] == char2[j])
                            dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + 1);
                    }
                }
            }
            return dp;
        }
    
        public static String lcse(String str1,String str2,int[][] dp){
            char[] char1 = str1.toCharArray();
            char[] char2 = str2.toCharArray();
            int m = char1.length-1;
            int n = char2.length-1;
            char[] res = new char[dp[m][n]];
            int index = res.length-1;
            while(index >= 0){
                if(n>0 && dp[m][n] == dp[m][n-1])
                    n--;
                else if(m>0 && dp[m-1][n] == dp[m][n])
                    m--;
                else{
                    res[index--] = char1[m];
                    m--;
                    n--;
                }
            }
            return String.valueOf(res);
        }
    
        public static void main(String[] args){
            String str1 = "1A2C3D4B56";
            String str2 = "B1D23CA45B6A";
    
            int[][] dp = findLongestSubStrDP(str1,str2);
            String res = lcse(str1,str2,dp);
            System.out.println(res);
        }
    }

# 7、最长公共子串 #

![Image 1][]

子串和子序列是不一样的， 子串必须是连续的，而子序列可以是不连续的。按照经典的动态规划方法，我们得到如下思路：

![Image 1][]

但题目中要求的空间复杂度是O(1)，因此我们按照如下的思路，得到了正确的解决方法：

![Image 1][]

package DynamicProgramming;
    
    public class LongestCommonSubString {
    
        public static String getLongestCommonSubString(String str1,String str2){
            if(str1==null || str2==null || str1.equals("") || str2.equals("")){
                return "";
            }
            char[] char1 = str1.toCharArray();
            char[] char2 = str2.toCharArray();
    
            int row = 0;
            int col = char2.length-1;
            int max = 0;
            int end = 0;
            while(row < char1.length){
                int i = row;
                int j = col;
                int len = 0;
                while(i<char1.length && j<char2.length){
                    if(char1[i] == char2[j]){
                        len++;
                    }
                    else{
                        len = 0;
                    }
                    if(len > max){
                        max = len;
                        end = I;
                    }
                    I++;
                    j++;
                }
                if(col > 0){
                    col--;
                }
                else{
                    row++;
                }
            }
            return str1.substring(end - max + 1,end + 1);
        }
    
        public static void main(String[] args){
            String str1 = "1AB2345CD";
            String str2 = "12345EF";
            System.out.println(getLongestCommonSubString(str1,str2));
        }
    }

# 8、最小编辑代价 #

![Image 1][]

这里为什么会增加一列和一行，因为字符串是可以删除为空串，然后再通过插入操作来进行变换的，如果没有空串，会得到错误的答案。

package DynamicProgramming;
    
    public class MinEditCost {
    
        public static int getMinEditCost(String str1,String str2,int ic,int dc,int rc){
            if(str1==null || str2==null)
                return 0;
            char[] char1 = str1.toCharArray();
            char[] char2 = str2.toCharArray();
    
            int[] dp = new int[char2.length+1];
            for(int j=0;j<char2.length+1;j++){
                dp[j] = j * ic;
            }
            for(int i=1;i<char1.length+1;i++){
                int pre = dp[0];
                dp[0] = dc * I;
                for(int j=1;j<char2.length+1;j++){
                    int tmp = dp[j];
                    if(char1[i-1] == char2[j-1]){
                        dp[j] = pre;
                    }
                    else{
                        dp[j] = pre + rc;
                    }
                    dp[j] = Math.min(dp[j],dp[j-1] + ic);
                    dp[j] = Math.min(dp[j],tmp + dc);
                    pre = tmp;
                }
            }
            return dp[char2.length];
        }
    
        public static void main(String[] args){
            String str1 = "abc";
            String str2 = "adc";
            int ic = 5;
            int dc = 3;
            int rc = 2;
    
            if(str1.length() >= str2.length())
                System.out.println(getMinEditCost(str1,str2,ic,dc,rc));
            else
                System.out.println(getMinEditCost(str2,str1,ic,dc,rc));
        }
    }

# 9、龙与地下城游戏问题 #

![Image 1][]

与前面的题目不同的地方是，我们这里采用从右下角往左上角遍历的顺序。但是动态规划的思想都是一样的。

package DynamicProgramming;
    
    public class MinHP {
    
        public static int getMinHP(int[][] arr){
            if(arr==null || arr.length==0 || arr[0].length==0)
                return 0;
            int[] dp = new int[arr[0].length];
            for(int i=arr.length-1;i>=0;i--){
                for(int j=arr[0].length-1;j>=0;j--){
                    if(i == arr.length-1 && j==arr[0].length-1)
                        dp[j] = arr[i][j] > 0 ? 1:1-arr[i][j];
                    else if(i==arr.length-1)
                        dp[j] = arr[i][j] > 0 ? dp[j+1]:dp[j+1] - arr[i][j];
                    else if(j==arr[0].length-1)
                        dp[j] = arr[i][j] > 0 ? dp[j]:dp[j] - arr[i][j];
                    else
                        dp[j] = arr[i][j] > 0 ? Math.min(dp[j],dp[j+1]) : Math.min(dp[j],dp[j+1]) - arr[i][j];
                }
            }
            return dp[0];
        }
    
        public static void main(String[] args){
            int[][] arr = {
                    {-2,-3,3},
                    {-5,-10,1},
                    {0,30,-5}};
            System.out.println(getMinHP(arr));
        }
    }

# 10、表达式得到期望结果的组成种数 #

![Image 1][]

首先判断express是否合理：

![Image 1][]

随后使用动态规划的方法：

![Image 1][]

package DynamicProgramming;
    
    public class DesiredExpressionNum {
        public static boolean isValid(char[] exp){
            if((exp.length & 1) == 0)
                return false;
            for(int i=0;i<exp.length;i+=2){
                if((exp[i] != '1') && (exp[i] != '0')){
                    return false;
                }
            }
            for(int i=1;i<exp.length;i+=2){
                if((exp[i] != '&') && (exp[i] != '|') && (exp[i]) != '^'){
                    return false;
                }
            }
            return true;
        }
    
        public static int getDesiredExpressionNum(String express,boolean desired){
            if(express == null || express.equals(""))
                return 0;
            char[] exp = express.toCharArray();
            if(!isValid(exp))
                return 0;
            int[][] t = new int[exp.length][exp.length];//t[j][i] 表示express[j][i] 组成true的个数
            int[][] f = new int[exp.length][exp.length];//f[j][i] 表示express[j][i] 组成false的个数
            t[0][0] = exp[0] == '0' ? 0:1;
            f[0][0] = exp[0] == '1' ? 0:1;
            for(int i=2;i<exp.length;i+=2){
                t[i][i] = exp[i] == '0'?0:1;
                f[i][i] = exp[i] == '1'?0:1;
                for(int j = i-2;j>=0;j-=2){
                    for(int k = j;k<i;k+=2){
                        if(exp[k+1] == '&'){
                            t[j][i] += t[j][k] * t[k+2][I];
                            f[j][i] += (f[j][k] + t[j][k]) * f[k+2][i] + f[j][k] * t[k+2][I];
                        }
                        else if(exp[k+1] == '|'){
                            t[j][i] += t[j][k] * f[k+2][i] + t[j][k] * t[k+2][i] + f[j][k] * t[k+2][I];
                            f[j][i] += f[j][k] * f[k+2][I];
                        }
                        else{
                            t[j][i] += f[j][k] * t[k+2][i] + t[j][k] * f[k+2][I];
                            f[j][i] += t[j][k] * t[k+2][i] + f[j][k] * f[k+2][I];
                        }
                    }
                }
            }
            return desired?t[0][exp.length-1]:f[0][exp.length-1];
        }
    
        public static void main(String[] args){
            String express = "1^0|0|1";
            Boolean desired = false;
            System.out.println(getDesiredExpressionNum(express,desired));
        }
    }

# 11、排成一条线的纸牌博弈游戏 #

![Image 1][]

package DynamicProgramming;
    
    public class CardGameScore {
    
        public static int getWinnerScore(int[] arr){
            if(arr==null || arr.length==0)
                return 0;
            int[][] f = new int[arr.length][arr.length];
            int[][] s = new int[arr.length][arr.length];
            for(int j = 0;j<arr.length;j++){
                f[j][j] = arr[j];
                for(int i = j-1;i>=0;i--){
                    f[i][j] = Math.max(s[i+1][j] + arr[i],s[i][j-1] + arr[j]);
                    s[i][j] = Math.min(f[i+1][j],f[i][j-1]); //对手也是聪明决定的，我们能够得到的是min的结果，取决于对方拿牌的情况。
                }
            }
            return Math.max(f[0][arr.length-1],s[0][arr.length-1]);
        }
    
        public static void main(String[] args){
            int[] arr = {1,2,100,4};
            System.out.println(getWinnerScore(arr));
        }
    }

# 12、跳跃问题 #

![Image 1][]

package DynamicProgramming;
    
    public class JumpGame {
        public static int getMinJumpTimes(int[] arr){
            if(arr==null || arr.length==0)
                return 0;
            int times=0,cur=0,next=0;
            for(int i=0;i<arr.length;i++){
                if(cur < i){
                    times ++;
                    cur = next;
                }
                next = Math.max(next,i + arr[I]);
            }
            return times;
        }
    
        public static void main(String[] args){
            int[] arr = {3,2,3,1,1,4};
            System.out.println(getMinJumpTimes(arr));
        }
    }

# 13、N皇后问题 #

![Image 1][]

著名的N皇后问题，我们给出一种基于递归的方法。这里我们用了一个小trick，即用一个一维数组保存每一行皇后的问题，这样，我们就可以只判断列活着斜线上是否已经放置了皇后即可。

package DynamicProgramming;
    
    public class NQueenV1 {
        public static boolean isValid(int row,int col,int[] record){
            for(int i=0;i<row;i++){
                if(record[i] == col || Math.abs(row-i) == Math.abs(record[i] - col))
                    return false;
            }
            return true;
        }
    
        public static int totalMethod(int index,int n,int[] record){
            if(index == n){
                return 1;
            }
            int res = 0;
    
            for(int j =0;j<n;j++){
                if(isValid(index,j,record)){
                    record[index] = j;
                    res += totalMethod(index + 1,n,record);
                }
            }
            return res;
        }
    
        public static void main(String[] args){
            int n = 8;
            int[] record = new int[n];
            System.out.println(totalMethod(0,n,record));
    
        }
    }

# 动态规划的适用条件 #

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

### 1.最优化原理（最优子结构性质） ###

最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

### 2.无后向性 ###

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

### 3.子问题的重叠性 ###

动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于**解决冗余**，这是动态规划算法的根本目的。

动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

以[Bitonic旅行路线问题][Bitonic]为例，这个问题也可以用搜索算法来解决。动态规划的时间复杂度为O(n2)，搜索算法的时间复杂度为O(n!) ，但从空间复杂度来看，动态规划算法为O(n2)，而搜索算法为O(n)，搜索算法反而优于动态规划算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

设原问题的规模为n，容易看出，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。

[Image 1]: 
[Bitonic]: http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/technique/dynamic_programming/chapter3.htm#example3