leetcode 剑指offer刷题归类之 二 动态规划篇

最长公共子串

1.给定两个字符串A和B，同时给定两串的长度n和m。

测试样例："1AB2345CD",9,"12345EF",7      返回：4

public class LongestSubstring {
    //最长公共子串要求是连续的
    public int findLongest(String A, int n, String B, int m) {
        int max = 0;
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    max = dp[i][j] > max ? dp[i][j] : max;
                }
            }
        return max;
    }
}

最长公共子序列

public class Zcggzul {
    //最长公共子序列不需要连续
    public static void main(String[] args) {

        String str1 = "1A2C3D4B56";
        String str2 = "B1D23CA45B6A";

        int m = str1.length()-1;
        int n = str2.length()-1;

        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();

        int[][] dp = getdp(chs1,chs2);


        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][n] == dp[m-1][n]){
                    m--;
                }else {
                    res[index--] = chs1[m];
                    m--;
                    n--;
                }
            }
        }

        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i]);

        }
        System.out.println();
    }



    public static int[][] getdp(char[] str1,char[] str2){
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0]==str2[0]?1:0;
        for (int i = 1; i < str1.length ; i++) {
            dp[i][0] = Math.max(dp[i-1][0],str1[i] == str2[0]?1:0);
        }
        for (int i = 1; i < str2.length; i++) {
            dp[0][i] = Math.max(dp[0][i-1],str1[0] == str2[i]?1:0);
            
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                if(str1[i] == str2[j]){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);

                }
                
            }

        }
        return dp;


    }

 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

0-n之间的数，少了其中一个，怎么找到少的那个

可以用异或

==============================================================================================================

最长回文字串问题

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。
测试样例：

"abc1234321ab",12

返回：7

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        int[][] dp = new int[n][n];
        int max = 1;
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }
        char[] a = A.toCharArray();
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                if (len == 2 && a[i] == a[j]) {
                    dp[i][j] = len;
                    max = 2;
                    continue;
                }
                if (a[i] == a[j] && dp[i + 1][j - 1] != 0) {
                    dp[i][j] = len;
                    max = len;
                }
            }
        }
        return max;
    }
}

动态规划
1.dp[i][j]表示，若i到j已经是回文串了，那么dp[i][j]是回文串的长度，否则为0；
2.初始时dp[i][i]=1，i=0,2,3...n-1；
3.递归公式，len>2时，当dp[i+1][j-1]!=0,且a[i]==a[j]时，dp[i][j] = j-i+1+dp[i+1][j-1],  否则dp[i][j]=0，i<j。这是一个从已知回文串往两边展开的过程。

当len=2时，特殊处理一下，因为当len=2时，dp[i+1][j-1]会访问到dp矩阵的左下方，我们没对那个位置做初始化处理，因此不能直接用递推公式

--------------------------------------------------------------------------------------------------------------------------------------------------------------

最长上升子序列

对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，

给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。

测试样例：

[2,1,4,3,1,5,6],7

时间复杂度为O（N2）的方法如下

public class ZuiChangDiZengZiXulie {


    public static void main(String[] args) {
        int[] arr = {2,1,5,3,6,4,8,9,7};
        int[] dp = getdp1(arr);

        int[] lis = generateLIS(arr,dp);
        for (int i = 0; i < lis.length; i++) {
            System.out.println(lis[i]);

        }

    }

    public static int[] generateLIS(int[] arr,int[] dp){
        int len = arr.length;
        int max = Integer.MIN_VALUE;
        int pos = 0;
        for (int i = 0; i < len; i++) {
            if(dp[i]>max){
                max = dp[i];
                pos = i;
            }
        }
        int[] tmp = new int[max];

        tmp[max-1] = arr[pos];
        max--;

        for (int i = pos-1; i >=0 ; i--) {
            if(dp[i] == max){
                tmp[max-1] = arr[i];
                max--;

            }

        }
        return tmp;

    }

    /*
      获取最长递增子序列长度
     */

    public static int[] getdp1(int[] arr){
        int[] dp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if(arr[i]>arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }

            }
        }
        return dp;
    }
}

时间复杂度为O（NlogN）的方法如下

public class AscentSequence {
    public static void main(String[] args) {
        int[] test = {2, 1, 4, 3, 1, 5, 6};
        AscentSequence as = new AscentSequence();
        System.out.println(as.findLongest(test));
    }

    public int findLongest(int[] arr) {
        int length = arr.length;
        int cur = 0;
        int[] tmp = new int[length];
        tmp[0] = arr[0];
        for (int i = 1; i < length; i++) {
            if (arr[i] > tmp[cur]) {
                tmp[++cur] = arr[i];
            } else {
                int pos = findpos(tmp, arr[i], 0, cur);
                tmp[pos] = arr[i];
            }
        }
        return cur + 1;
    }

    //寻找num在数组中的位置
    private int findpos(int[] tmp, int num, int start, int end) {
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (tmp[mid] == num) {
                return mid;
            }
            if (tmp[mid] < num) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

/*下面一步一步试着找出它。

我们定义一个序列B，然后令i = 0到8逐个考察这个序列。

此外，我们用一个变量end来记录B中最后一个数的下标。

首先，令B[0] = A[0] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2，这时end=0。

然后，把A[2]有序地放到B里，令B[0] = 1，就是说长度为1的LIS的最小末尾是1，B[0]=2已经被淘汰了，这时end =1。

接着，A[2] = 5，A[2]>B[0]，所以令B[1]=A[2]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候B[0..1] = 1, 5， end＝1。

再来，A[3] = 3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，

长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候B[0..1] = 1, 3， end = 2。

继续，A[4] = 6，比B中最大的数3还要大 ，于是很容易可以推知B[2] = 6, 这时B[0..2] = 1, 3, 6，end = 2。

A[5] = 4，它在3和6之间，于是我们就要把6替换掉，得到B[2] = 4，B[0..2] = 1, 3, 4，end继续等于2。

A[6] = 8，它很大，比4大。于是继续往B中追加，B[3] = 8， end变成3了。

A[7] = 9，得到B[4] = 9，此时B是1,3,4,8,9，end是4。

最后一个, A[8] = 7，它在4和8之间，所以我们知道，最新的B[3] =7，B[0..4] = 1, 3, 4, 7, 9，end = 4。

于是我们知道了LIS的长度为end+1 = 5。

注意： 这个1,3,4,7,9不是LIS字符串，比如本题例的LIS应该是1,3,4,8,9，7代表的意思是存储4位长度LIS的最小末尾是7，

所以我们的B数组，是存储对应长度LIS的最小末尾。有了这个末尾，我们就可以一个一个地插入数据。

虽然最后一个A[8] = 7更新进去对于这组数据没有什么意义，但是如果后面再出现两个数字8和9，

那么就可以把8更新到B[4], 9更新到B[5]，得出LIS的长度为6。

然后应该发现一件事情了：在B中插入数据是有序的，而且是进行替换而不需要挪动——也就是说，我们可以使用 二分查找 ，

将每一个数字的插入时间优化到 O(logN)，于是算法的时间复杂度就降低到了O(NlogN)。*/

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

连续子数组的最大和

public class MaxNumber {
public static void main(String[] args) {
	int A[]=new int[]{2,1,-4,3,-1,5,6};
	System.out.println(biggest(A,7));
}
public static  int biggest(int[] A,int length){
	int MaxSum=0;
	int CurSum=0;
	for(int i=0;i<length;i++){
		CurSum+=A[i];
		if(CurSum>MaxSum){
			MaxSum=CurSum;	
		}
		if(CurSum<0)
			CurSum=0;
	}	
	return MaxSum;
}
}

换钱的方法数

public class HuanQianDeFangFaShu {

    public static void main(String[] args) {
        int[] arr = {5,10,25,1};
        System.out.println(coin3(arr,50));



    }

    /*
    普通解法
     */

    public int coins1(int[] arr,int aim){

        if(arr == null || arr.length == 0 || aim<0){
            return 0;
        }
        return process1(arr,0,aim);

    }
    private int process1(int[] arr,int index,int aim){
        int res = 0;
        if(index == arr.length){
            res = aim==0?1:0;
        }else {
            for (int i = 0; arr[index]*i <= aim ; i++) {
                res += process1(arr,index+1,aim-arr[index]*i);

            }
        }
        return res;

    }




    /*
    动态规划解法
     */
    public static int coin3(int[] arr,int aim){
        if(arr == null || arr.length == 0 || aim<0){
            return 0;
        }

        int[][] dp = new int[arr.length][aim+1];

        /**
         * dp[][0]组成钱数为0的方法数，很明显都是1种，也就是
         * 不使用任何货币
         */
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;

        }
        /**
         * dp[0][],只使用第一种货币的话，第一种货币的整数倍是1
         * 其他的为0
         */

        for (int i = 1; arr[0]*i <=aim ; i++) {
            dp[0][arr[0]*i] = 1;

        }

        int num = 0;
        for (int i = 1; i < arr.length ; i++) {
            for (int j = 1; j <=aim ; j++) {
                num = 0;
                /**
                 * 完全不用arr[i]货币，方法数为arr[i-1][j]
                 * 用一张arr[i],剩下的由arr[0...i-1]组成
                 *方法数为dp[i-1][j-n*arr[i]]

                 */
                for (int k = 0; k*arr[i] <= j ; k++) {
                    num += dp[i-1][j-arr[i]*k];

                }
                dp[i][j] = num;

            }

        }
        return dp[arr.length-1][aim];


    }


}

解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

1.递归暴力解法

public static int process(char[] chs,int i){
        //递归终止条件
        if(i == chs.length){
            return 1;
        }
        //不可能以0开头
        if(chs[i] == '0'){
            return 0;
        }
        int res = process(chs, i+1);
        if(i+1<chs.length&&(chs[i]-'0')*10+chs[i+1]-'0'<27){
            res+=process(chs, i+2);
        }
        return res;
    }

2.动态规划解法

动态规划关键在于每个阶段状态的把握。

举个例子，比如12224，我们首先对第一位，只能1这种解码方法。

对第二位2，可以1-2（独立），也可以12（合并），两种解码方法。

对第三位2，可以1-2-2（独立），也可以12-2（独立），也可以1-22（合并），三种解码方法。

在这一步我们发现其实到当前位为止的解码方法个数，就是上一步的解码方法个数（在后面直接添加独立的一位）+上一步独立的个数（当然这里要判断能不能合并在一起）。

所以我们只需要记住上一步的解码方法个数和上一步的独立的个数，就可以分不同阶段去处理。

再接下来对第四位2，可以1-2-2-2，也可以12-2-2，也可以1-22-2，这三个都是直接在后面添加独立的一位，也可以1-2-22，也可以12-22，这两个就是把先前独立的一位给合并了，所以当前总的解码个数是3+2=5，当前独立的个数就是3，也是上一步的总解码个数。

过程如下：

规律十分清晰，但我们还有一个情况没有考虑到，就是可能会出现数字0。

比如110，第二个1这一步，当前总的解码方式有1-1和11，两种，独立可合并下一位的个数有一种。

然后到了0这一步，只能合并了，于是总的解码方式变成上一步独立可合并下一位的个数1，解码方式是1-10，当前这一位的独立可合并个数清空为0。

那还有不能合并的呢，比如130，3这一步，仍然是1-3和13，总的有2种，独立的有1种。

到0这一步，不能合并，于是总的解码方式变成0，完全不能解码，返回0。

public static int numDecodings(String s) {

        if(s == null || s.length()==0 || s.charAt(0)=='0'){
            return 0;
        }

        //merge 当前可独立合并下一位的个数，既直接把数字加到前面的末尾时。
        //total 总的解码个数
        int merge = 1,total = 1,sum1,tmp;
        for (int i = 1; i <s.length() ; i++) {
            //和前一位合并的值
            sum1 = ((s.charAt(i-1)-'0')*10+(s.charAt(i)-'0'));

            //如果数值符合条件，那么可以合并
            if(sum1>=1&&sum1<=26){
                if(s.charAt(i)!='0'){
                    tmp = total;
                    //总的解码个数有联股份组成1.直接把数字加到末尾的，就是total。第二与前面的末尾合并。就是merge
                    total+= merge;
                    //merge应该变成当前的total
                    merge = tmp;
                }else {
                    //当亲位为0，只能与前面的合并
                    total = merge;
                    merge = 0;

                }

            }else {

                //计算出不能合并
                if(s.charAt(i)!='0'){ //当前位置不是0的话，可以直接把数字加到末尾
                    merge = total;

                }else {   //当前位置为0，既不能加到末尾，又不能合并
                    return 0;
                }

            }


        }
        return total;

    }

leetcode 72. 编辑距离

public int minDistance1(String word1, String word2) {
        if (word1 == null && word2 == null) {
            return 0;
        }
        if (word1 == null || word1.length() == 0) {
            return word2.length();
        }
        if (word2 == null || word2.length() == 0) {
            return word1.length();
        }
        int row = word1.length() + 1;
        int col = word2.length() + 1;
        //dp[i][j] word1的前i个字符变成word2的前j个字符的距离
        int[][] dp = new int[row][col];
        //空串的时候，   把字符全删了
        for (int i = 0; i < row; i++) {
            dp[i][0] = i;
        }

        //全加上
        for (int i = 0; i < col; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //替换
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                //删除
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j]);
                //增加
                dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i][j]);

            }

        }

        return dp[row - 1][col - 1];

    }


//空间压缩

public int minDistance(String word1, String word2) {
        if (word1 == null && word2 == null) {
            return 0;
        }
        if (word1 == null || word1.length() == 0) {
            return word2.length();
        }
        if (word2 == null || word2.length() == 0) {
            return word1.length();
        }
        int row = word1.length() + 1;
        int col = word2.length() + 1;
        //dp[i][j] word1的前i个字符变成word2的前j个字符的距离
        int[][] dp = new int[2][col];

        //全加上
        for (int i = 0; i < col; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i < row; i++) {
            dp[i % 2][0] = dp[(i - 1) % 2][0] + 1;
            for (int j = 1; j < col; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1];
                } else {
                    //替换
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
                }
                //删除
                dp[i % 2][j] = Math.min(dp[(i - 1) % 2][j] + 1, dp[i % 2][j]);
                //增加
                dp[i % 2][j] = Math.min(dp[i % 2][j - 1] + 1, dp[i % 2][j]);

            }

        }

        return dp[(row-1) % 2][col - 1];

    }

    

最小编辑代价

public int minCost1(String str1,String str2,int ic,int dc,int rc){
        if(str1 == null||str2 == null){
            return 0;
        }
        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        int row = chs1.length+1;
        int col = chs2.length+1;
        //dp[i][j]表示str1[0...i]编辑成str2[0...j-1]的最小代价
        int[][] dp = new int[row][col];
        //变成空串当然是删除所有字符
        for (int i = 0; i < row; i++) {
            dp[i][0] = dc*i;
        }
        //由空串变成现在的字符串当然是一直加字符
        for (int i = 0; i < col; i++) {
            dp[0][i] = ic*i;
        }
        for (int i = 0; i < row ; i++) {
            for (int j = 0; j < col; j++) {
                if(chs1[i-1] == chs2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = dp[i-1][j-1]+rc;
                }
                dp[i][j] = Math.min(dp[i][j],dp[i][j-1]+ic);
                dp[i][j] = Math.min(dp[i][j],dp[i-1][j]+dc);

            }

        }
        return dp[row-1][col-1];
    }

找零钱问题

    【题目】给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。

【举例】

arr=[5,10,25,1]，aim=0。组成0元的方法有1种，就是所有面值的货币都不用。所以返回1。

arr=[5,10,25,1]，aim=15。组成15元的方法有6种，分别为3张5元，1张10元+1张5元，1张10元+5张1元，10张1元+1张5元，2张5元+5张1元，15张1元。所以返回6。

arr=[3,5]，aim=2。任何方法都无法组成2元。所以返回0。
 

 public static int coinChange(int[] coins, int amount) {

        int max = amount + 1;
        int[] dp = new int[amount + 1];
        for (int i = 0; i < dp.length ; i++) {
            dp[i] = max;

        }
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    //其实和跳台阶思路差不多，可以跳上给定的任一级
                    //因此这里就是选这次到期用哪种钱可以使得当前值最小
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }

            }

        }
        return dp[amount] > amount ? -1 : dp[amount];

    }

leetcode 120. 三角形最小路径和

 /**
     * 分析：考虑自底向上的解法简单点，
     * 动态转移方程为：
     * dp[m][n] = min(dp[m + 1][n], dp[m + 1][n + 1]) + triangle[m][n].
     */
    public int minimumTotal(int[][] triangle){
        if(triangle == null || triangle.length == 0){
            return 0;
        }
        int row = triangle.length;
        int[] dp = new int[row];
        for (int i = 0; i < row ; i++) {
            dp[i] = triangle[row-1][i];
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = 0; j <= i ; j++) {
                dp[j] = triangle[i][j]+Math.min(dp[j], dp[j+1]);
            }

        }
        return dp[0];
    }

空间压缩

public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null || triangle.size() == 0){
            return 0;
        }
        int len = triangle.size();
        int[] dp = new int[len+1];
        int tmp1;
        for (int i = len-1; i >= 0 ; i--) {
            int tmp2 = dp[i+1];
            for (int j = i; j >= 0 ; j--) {
                tmp1 = dp[j];
                dp[j] = Math.min(tmp2,dp[j])+triangle.get(i).get(j);
                tmp2 = tmp1;
            }

        }
        return dp[0];
    }

乘积最大子序列

public int maxProduct(int[] nums){

        int[] maxdp = new int[nums.length];
        int[] mindp = new int[nums.length];
        maxdp[0] = maxdp[0] = nums[0];
        for (int i = 1; i < nums.length ; i++) {
            if (nums[i] >= 0) {
                maxdp[i] = Math.max(maxdp[i - 1] * nums[i], nums[i]);
                mindp[i] = Math.min(mindp[i - 1] * nums[i], nums[i]);
            }else {
                maxdp[i] = Math.max(mindp[i - 1] * nums[i], nums[i]);
                mindp[i] = Math.min(maxdp[i - 1] * nums[i], nums[i]);
            }
        }
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < maxdp.length ; i++){
            if(maxdp[i] > result){
                result = maxdp[i];
            }
        }
        return result;
    }

leetcode 64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。示例: 输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

如果申请一个二维空间的dp[][],那么状态转移方程为dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);

 public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }

        for (int i = 1; i < col; i++) {
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {

                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[row - 1][col - 1];
    }

    //空间压缩
    public int minPathSum1(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int[] dp = new int[col];
        //初始化第一行
        dp[0] = grid[0][0];
        for (int i = 1; i < col; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }
        for (int i = 1; i < row; i++) {
            dp[0] = grid[i][0] + dp[0];
            for (int j = 1; j < col; j++) {
                dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
            }
        }
        return dp[col - 1];
    }

leetcode 63. 不同路径 II

/**
     * 空间压缩
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
            return 0;
        }
        int[] dp = new int[col];
        dp[0] = 1;
        for (int i = 1; i < col; i++) {
            if (dp[i - 1] == 0 || obstacleGrid[0][i] == 1) {
                dp[i] = 0;
            } else {
                dp[i] = 1;
            }
        }

        for (int i = 1; i < row; i++) {
            if (dp[0] == 1 && obstacleGrid[i][0] == 0) {
                dp[0] = 1;
            }else {
                dp[0] = 0;
            }

            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else {
                    dp[j] = dp[j - 1] + dp[j];
                }
            }

        }
        return dp[col - 1];
    }


    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
            return 0;
        }
        int[][] dp = new int[row][col];
        dp[0][0] = 1;
        for (int i = 1; i < row; i++) {
            if (dp[i - 1][0] == 0 || obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;
            } else {
                dp[i][0] = 1;
            }
        }

        for (int i = 1; i < col; i++) {
            if (dp[0][i - 1] == 0 || obstacleGrid[0][i] == 1) {
                dp[0][i] = 0;
            } else {
                dp[0][i] = 1;
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }

        }
        return dp[row - 1][col - 1];
    }