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)的解法

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

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、矩阵的最短路径和

使用动态规划的方法，建立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 每种货币数量无限

在每种货币数量无限的情况下，使用动态规划的方法，从二维数组的角度出发，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张

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

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、换钱的方法数

这里要注意的一点是，组成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、最长递增子序列

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、最长公共子序列问题

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、最长公共子串

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

但题目中要求的空间复杂度是O(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、最小编辑代价

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

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、龙与地下城游戏问题

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

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、表达式得到期望结果的组成种数

首先判断express是否合理：

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

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、排成一条线的纸牌博弈游戏

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、跳跃问题

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皇后问题

著名的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));

    }
}