第9章動态規劃基礎

很多同學聽到“動态規劃”的名稱可能會望而生畏，覺得動态規劃的問題都很複雜。但其實，動态規劃本質依然是遞歸算法，隻不過是滿足特定條件的遞歸算法。在這一章裡，我們就來逐漸解開動态規劃的神秘面紗目錄

9-1 什麼是動态規劃

9-2 第一個動态規劃問題 Climbing Stairs

9-3 發現重疊子問題 Integer Break

9-4 狀态的定義和狀态轉移 House Robber

9-5 0-1背包問題

9-6 0-1背包問題的優化和變種

9-7 面試中的0-1背包問題 Partition Equal Subset Sum

9-8 LIS問題 Longest Increasing Subsequence

9-9 LCS，最短路，求動态規劃的具體解以及更多

9-1 什麼是動态規劃

記憶化搜尋–自上而下的解決問題

動态規劃–自下而上的解決問題

動态規劃：将原問題拆解成若幹子問題，同時儲存子問題的答案，使得每個子問題隻求解一次，最終獲得原問題的答案。

遞歸問題--------重疊子問題

記憶化搜尋--------自頂向下的解決問題

動态規劃--------自底向上的解決問題

最優子結構：通過求子問題的最優解，可以獲得原問題的最優解。

遞歸問題--------重疊子問題 + 最優子結構

記憶化搜尋--------自頂向下的解決問題

動态規劃--------自底向上的解決問題

題目: 斐波那契數列指的是這樣一個數列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……

特别指出：第0項是0，第1項是第一個1。

這個數列從第三項開始，每一項都等于前兩項之和。

// 遞歸求斐波那契數列
public class Solution1 {

    private int num = 0;

    public int fib( int n ){

        num ++;

        if( n == 0 )
            return 0;

        if( n == 1 )
            return 1;

        return fib(n-1) + fib(n-2);
    }

    public int getNum(){
        return num;
    }

    public static void main(String[] args) {

        int n = 50;

        Solution1 solution = new Solution1();
        long startTime = System.currentTimeMillis();
        int res = solution.fib(n);
        long endTime = System.currentTimeMillis();        System.out.println("fib(" + n + ") = " + res);
        System.out.println("time : " + (endTime - startTime) + " ms");
        System.out.println("run function fib() " + solution.getNum() + " times.");
    }
}

import java.util.Arrays;

// 記憶化搜尋
public class Solution2 {

    private int num = 0;

    public int fib(int n){

        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return fib(n, memo);
    }

    private int fib(int n, int[] memo){

        num ++;

        if(n == 0)
            return 0;

        if(n == 1)
            return 1;

        if(memo[n] == -1)
            memo[n] = fib(n - 1, memo) + fib(n - 2, memo);

        return memo[n];
    }

    public int getNum(){
        return num;
    }

    public static void main(String[] args) {

        //int n = 42;
        int n = 42; // 注意: 我們使用n = 1000隻是為了測試性能, 實際上會溢出
                      // 斐波那契額數列是以指數速度上漲的

        Solution2 solution = new Solution2();
        long startTime = System.currentTimeMillis();
        int res = solution.fib(n);
        long endTime = System.currentTimeMillis();        System.out.println("fib(" + n + ") = " + res);
        System.out.println("time : " + (endTime - startTime) + " ms");
        System.out.println("run function fib() " + solution.getNum() + " times.");
    }
}

import java.util.Arrays;

// 動态規劃
public class Solution3 {

    public int fib(int n){

        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);

        memo[0] = 0;
        memo[1] = 1;
        for(int i = 2 ; i <= n ; i ++)
            memo[i] = memo[i - 1] + memo[i - 2];

        return memo[n];
    }

    public static void main(String[] args) {

        //int n = 42;
        int n = 1000; // 注意: 我們使用n = 1000隻是為了測試性能, 實際上會溢出
                      // 斐波那契額數列是以指數速度上漲的

        Solution3 solution = new Solution3();
        long startTime = System.currentTimeMillis();
        int res = solution.fib(n);
        long endTime = System.currentTimeMillis();

        System.out.println("fib(" + n + ") = " + res);
        System.out.println("time : " + (endTime - startTime) + " ms");
    }
}

9-2 第一個動态規劃問題 Climbing Stairs

題目: LeetCode 70. 爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例 1：

輸入： 2

輸出： 2

解釋：有兩種方法可以爬到樓頂。

1 階 + 1 階

2 階

示例 2：

輸入： 3

輸出： 3

解釋：有三種方法可以爬到樓頂。1 階 + 1 階 + 1 階

1 階 + 2 階

2 階 + 1 階

import java.util.Arrays;

public class Solution1 {

    private int[] memo;

    public int climbStairs(int n) {
        memo = new int[n+1];
        Arrays.fill(memo, -1);
        return calcWays(n);
    }

    private int calcWays(int n){

        if(n == 0 || n == 1)
            return 1;

        if(memo[n] == -1)
            memo[n] = calcWays(n - 1) + calcWays(n - 2);

        return memo[n];
    }

    public static void main(String[] args) {        System.out.println((new Solution1()).climbStairs(10));
    }

}

/// 70. Climbing Stairs
/// https://leetcode.com/problems/climbing-stairs/description/
/// 動态規劃
/// 時間複雜度: O(n)
/// 空間複雜度: O(n)
public class Solution2 {

    public int climbStairs(int n) {

        int[] memo = new int[n + 1];
        memo[0] = 1;
        memo[1] = 1;
        for(int i = 2 ; i <= n ; i ++)
            memo[i] = memo[i - 1] + memo[i - 2];
        return memo[n];
    }

    public static void main(String[] args) {

        System.out.println((new Solution2()).climbStairs(10));
    }
}

課後作業: LeetCode 120、64

9-3 發現重疊子問題 Integer Break

題目: LeetCode 343. 整數拆分

給定一個正整數 n，将其拆分為至少兩個正整數的和，并使這些整數的乘積最大化。傳回你可以獲得的最大乘積。

示例 1:

輸入: 2

輸出: 1

解釋: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

輸入: 10

輸出: 36

解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

說明: 你可以假設 n 不小于 2 且不大于 58。

/// 343. Integer Break
/// https://leetcode.com/problems/integer-break/description/
/// 暴力搜尋
/// 在Leetcode中送出這個版本的代碼會逾時! (Time Limit Exceeded)
/// 時間複雜度: O(n^n)
/// 空間複雜度: O(n)
public class Solution1 {

    public int integerBreak(int n) {

        if(n < 1)
            throw new IllegalArgumentException("n should be greater than zero");

        return breakInteger(n);
    }

    // 将n進行分割(至少分割兩部分), 可以獲得的最大乘積
    private int breakInteger(int n){

        if(n == 1)
            return 1;

        int res = -1;
        for(int i = 1 ; i <= n - 1 ; i ++)
            res = max3(res, i * (n - i), i * breakInteger(n - i));
        return res;
    }

    private int max3(int a, int b, int c){
        return Math.max(a, Math.max(b, c));
    }

    public static void main(String[] args) {        System.out.println((new Solution1()).integerBreak(2));
        System.out.println((new Solution1()).integerBreak(10));
    }
}

import java.util.Arrays;

/// 343. Integer Break
/// https://leetcode.com/problems/integer-break/description/
/// 記憶化搜尋
/// 時間複雜度: O(n^2)
/// 空間複雜度: O(n)
public class Solution2 {

    private int[] memo;

    public int integerBreak(int n) {

        if(n < 1)
            throw new IllegalArgumentException("n should be greater than zero");

        memo = new int[n+1];
        Arrays.fill(memo, -1);

        return breakInteger(n);
    }

    // 将n進行分割(至少分割兩部分), 可以獲得的最大乘積
    private int breakInteger(int n){

        if(n == 1)
            return 1;

        if(memo[n] != -1)
            return memo[n];

        int res = -1;
        for(int i = 1 ; i <= n - 1 ; i ++)
            res = max3(res, i * (n - i) , i * breakInteger(n - i));
        memo[n] = res;
        return res;
    }

    private int max3(int a, int b, int c){
        return Math.max(a, Math.max(b, c));
    }

    public static void main(String[] args) {        System.out.println((new Solution2()).integerBreak(2));
        System.out.println((new Solution2()).integerBreak(10));
    }
}

/// 343. Integer Break
/// https://leetcode.com/problems/integer-break/description/
/// 動态規劃
/// 時間複雜度: O(n^2)
/// 空間複雜度: O(n)
public class Solution3 {

    public int integerBreak(int n) {

        if(n < 1)
            throw new IllegalArgumentException("n should be greater than zero");

        int[] memo = new int[n+1];
        memo[1] = 1;
        for(int i = 2 ; i <= n ; i ++)
            // 求解memo[i]
            for(int j = 1 ; j <= i - 1 ; j ++)
                memo[i] = max3(memo[i], j * (i - j), j * memo[i - j]);

        return memo[n];
    }

    private int max3(int a, int b, int c){
        return Math.max(a, Math.max(b, c));
    }

    public static void main(String[] args) {

        System.out.println((new Solution3()).integerBreak(2));
        System.out.println((new Solution3()).integerBreak(10));
    }
}

課後作業: LeetCode 279、91、62、63

9-4 狀态的定義和狀态轉移 House Robber

題目: LeetCode 198. 打家劫舍

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入: [1,2,3,1]

輸出: 4

解釋: 偷竊 1 号房屋 (金額 = 1) ，然後偷竊 3 号房屋 (金額 = 3)。

偷竊到的最高金額 = 1 + 3 = 4 。

示例 2:

輸入: [2,7,9,3,1]

輸出: 12

解釋: 偷竊 1 号房屋 (金額 = 2), 偷竊 3 号房屋 (金額 = 9)，接着偷竊 5 号房屋 (金額 = 1)。

偷竊到的最高金額 = 2 + 9 + 1 = 12 。其中對“狀态”的定義：考慮偷取[x, n-1]範圍裡的房子（函數的定義）。

根據對狀态的定義，決定狀态的轉移：

f(0) = max{v(0) + f(2), v(1) + f(3), v(2) + f(4), …, v(n-3) + f(n-1), v(n-2) , v(n-1) }

import java.util.Arrays;

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 記憶化搜尋
/// 時間複雜度: O(n^2)
/// 空間複雜度: O(n)
public class Solution1 {

    // memo[i] 表示考慮搶劫 nums[i...n) 所能獲得的最大收益
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return tryRob(nums, 0);
    }

    // 考慮搶劫nums[index...nums.size())這個範圍的所有房子
    private int tryRob(int[] nums, int index){

        if(index >= nums.length)
            return 0;

        if(memo[index] != -1)
            return memo[index];

        int res = 0;
        for(int i = index ; i < nums.length ; i ++)
            res = Math.max(res, nums[i] + tryRob(nums, i + 2));
        memo[index] = res;
        return res;
    }

    public static void main(String[] args) {

        int nums[] = {2, 1};
        System.out.println((new Solution1()).rob(nums));
    }

import java.util.Arrays;

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 動态規劃
/// 時間複雜度: O(n^2)
/// 空間複雜度: O(n)
public class Solution2 {

    public int rob(int[] nums) {

        int n = nums.length;
        if(n == 0)
            return 0;

        // memo[i] 表示考慮搶劫 nums[i...n) 所能獲得的最大收益
        int[] memo = new int[nums.length];
        memo[n - 1] = nums[n - 1];
        for(int i = n - 2 ; i >= 0 ; i --)
            for (int j = i; j < n; j++)
                memo[i] = Math.max( memo[i],
                                    nums[j] + (j + 2 < n ? memo[j + 2] : 0));

        return memo[0];
    }

    public static void main(String[] args) {        int nums[] = {2, 1};
        System.out.println((new Solution2()).rob(nums));
    }
}

import java.util.Arrays;

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 記憶化搜尋, 改變狀态定義
/// 時間複雜度: O(n^2)
/// 空間複雜度: O(n)
public class Solution3 {

    // memo[i] 表示考慮搶劫 nums[0...i] 所能獲得的最大收益
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return tryRob(nums, nums.length - 1);
    }

    // 考慮搶劫nums[0...index]這個範圍的所有房子
    private int tryRob(int[] nums, int index){

        if(index < 0)
            return 0;

        if(memo[index] != -1)
            return memo[index];

        int res = 0;
        for(int i = 0 ; i <= index ; i ++)
            res = Math.max(res, nums[i] + tryRob(nums, i - 2));
        memo[index] = res;
        return res;
    }

    public static void main(String[] args) {        int nums[] = {2, 1};
        System.out.println((new Solution3()).rob(nums));
    }
}

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 動态規劃, 改變狀态定義
/// 時間複雜度: O(n^2)
/// 空間複雜度: O(n)
public class Solution4 {

    public int rob(int[] nums) {

        int n = nums.length;
        if(n == 0)
            return 0;

        // memo[i] 表示考慮搶劫 nums[0...i] 所能獲得的最大收益
        int[] memo = new int[nums.length];
        memo[0] = nums[0];
        for(int i = 1 ; i < n ; i ++)
            for (int j = i; j >= 0; j--)
                memo[i] = Math.max(memo[i],
                                   nums[j] + (j - 2 >= 0 ? memo[j - 2] : 0));

        return memo[n-1];
    }

    public static void main(String[] args) {        int nums[] = {2, 1};
        System.out.println((new Solution4()).rob(nums));
    }
}

import java.util.Arrays;

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 記憶化搜尋, 優化狀态轉移
/// 時間複雜度: O(n)
/// 空間複雜度: O(n)
public class Solution5 {

    // memo[i] 表示考慮搶劫 nums[i...n) 所能獲得的最大收益
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return tryRob(nums, 0);
    }

    // 考慮搶劫nums[index...nums.size())這個範圍的所有房子
    private int tryRob(int[] nums, int index){

        if(index >= nums.length)
            return 0;

        if(memo[index] != -1)
            return memo[index];

        // 或者目前房子放棄, 從下一個房子開始考慮
        // 或者搶劫目前的房子, 從i+2以後的房子開始考慮
        return memo[index] =
                Math.max(tryRob(nums, index + 1),
                         nums[index] + tryRob(nums, index + 2));
    }

    public static void main(String[] args) {        int nums[] = {2, 1};
        System.out.println((new Solution5()).rob(nums));
    }
}

import java.util.Arrays;

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 動态規劃, 優化狀态轉移
/// 時間複雜度: O(n)
/// 空間複雜度: O(n)
public class Solution6 {

    public int rob(int[] nums) {

        int n = nums.length;
        if(n == 0)
            return 0;

        // memo[i] 表示考慮搶劫 nums[i...n) 所能獲得的最大收益
        int[] memo = new int[nums.length];
        memo[n - 1] = nums[n - 1];
        for(int i = n - 2 ; i >= 0 ; i --)
            // 或者目前房子放棄, 從下一個房子開始考慮
            // 或者搶劫目前的房子, 從i+2以後的房子開始考慮
            memo[i] = Math.max(memo[i + 1],
                               nums[i] + (i + 2 < n ? memo[i + 2] : 0));

        return memo[0];
    }

    public static void main(String[] args) {        int nums[] = {2, 1};
        System.out.println((new Solution6()).rob(nums));
    }
}

import java.util.Arrays;

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 記憶化搜尋, 改變狀态定義, 優化轉移方程
/// 時間複雜度: O(n)
/// 空間複雜度: O(n)
public class Solution7 {

    // memo[i] 表示考慮搶劫 nums[0...i] 所能獲得的最大收益
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return tryRob(nums, nums.length - 1);
    }

    // 考慮搶劫nums[0...index]這個範圍的所有房子
    private int tryRob(int[] nums, int index){

        if(index < 0)
            return 0;

        if(memo[index] != -1)
            return memo[index];

        // 或者目前房子放棄, 考慮[0...index-1]的所有房子
        // 或者搶劫目前的房子, 考慮[0...index-2]的所有房子
        return memo[index] =
                Math.max(tryRob(nums, index - 1),
                         nums[index] + tryRob(nums, index - 2));
    }

    public static void main(String[] args) {        int nums[] = {2, 1};
        System.out.println((new Solution7()).rob(nums));
    }
}

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 動态規劃, 改變狀态定義, 優化轉移方程
/// 時間複雜度: O(n)
/// 空間複雜度: O(n)
public class Solution8 {

    public int rob(int[] nums) {

        int n = nums.length;
        if(n == 0)
            return 0;

        // memo[i] 表示考慮搶劫 nums[0...i] 所能獲得的最大收益
        int[] memo = new int[nums.length];
        memo[0] = nums[0];
        for(int i = 1 ; i < n ; i ++)
            memo[i] = Math.max(memo[i - 1],
                               nums[i] + (i - 2 >= 0 ? memo[i - 2] : 0));

        return memo[n-1];
    }

    public static void main(String[] args) {        int nums[] = {2, 1};
        System.out.println((new Solution8()).rob(nums));
    }
}

課後作業: LeetCode 213、337、309

9-5 0-1背包問題

題目: 有一個背包，它的容量為c(Capacity)。現在有n種不同的物品，編号為0…,n-1，其中每一件物品的重量為w(i)，價值為v(i)。

問可以向這個背包中盛放哪些物品，使得在不超過背包容量的基礎上，物品的總價值最大。

其中對“狀态”的定義：F(i, c)考慮将n個物品放入容量為c的背包，使得價值最大。

根據對狀态的定義，決定狀态的轉移：

F(i,c)=F(i-1,c)

=v(i)+F(i-1,c-w(i))

F(i, c) = max{F(i-1, c), v(i) + F(i-1, c - w(i))}

測試資料

/// 背包問題
/// 記憶化搜尋
/// 時間複雜度: O(n * C) 其中n為物品個數; C為背包容積
/// 空間複雜度: O(n * C)
public class Solution1 {

    private int[][] memo;

    public int knapsack01(int[] w, int[] v, int C){

        if(w == null || v == null || w.length != v.length)
            throw new IllegalArgumentException("Invalid w or v");

        if(C < 0)
            throw new IllegalArgumentException("C must be greater or equal to zero.");

        int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        memo = new int[n][C + 1];
        return bestValue(w, v, n - 1, C);
    }

    // 用 [0...index]的物品,填充容積為c的背包的最大價值
    private int bestValue(int[] w, int[] v, int index, int c){

        if(c <= 0 || index < 0)
            return 0;

        if(memo[index][c] != -1)
            return memo[index][c];

        int res = bestValue(w, v, index-1, c);
        if(c >= w[index])
            res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));

        return memo[index][c] = res;
    }

    public static void main(String[] args) {

    }

}

/// 背包問題
/// 動态規劃
/// 時間複雜度: O(n * C) 其中n為物品個數; C為背包容積
/// 空間複雜度: O(n * C)
public class Solution2 {

    public int knapsack01(int[] w, int[] v, int C){

        if(w == null || v == null || w.length != v.length)
            throw new IllegalArgumentException("Invalid w or v");

        if(C < 0)
            throw new IllegalArgumentException("C must be greater or equal to zero.");

        int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        int[][] memo = new int[n][C + 1];

        for(int j = 0 ; j <= C ; j ++)
            memo[0][j] = (j >= w[0] ? v[0] : 0 );

        for(int i = 1 ; i < n ; i ++)
            for(int j = 0 ; j <= C ; j ++){
                memo[i][j] = memo[i-1][j];
                if(j >= w[i])
                    memo[i][j] = Math.max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);
            }

        return memo[n - 1][C];
    }

    public static void main(String[] args) {    }
}

9-6 0-1背包問題的優化和變種

優化：跟進分析會發現，第i行元素隻依賴于第i-1行元素，理論上，隻需要保持兩行元素。

/// 背包問題
/// 動态規劃改進: 滾動數組
/// 時間複雜度: O(n * C) 其中n為物品個數; C為背包容積
/// 空間複雜度: O(C), 實際使用了2*C的額外空間
public class Solution1 {

    public int knapsack01(int[] w, int[] v, int C){

        if(w == null || v == null || w.length != v.length)
            throw new IllegalArgumentException("Invalid w or v");

        if(C < 0)
            throw new IllegalArgumentException("C must be greater or equal to zero.");

        int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        int[][] memo = new int[2][C + 1];

        for(int j = 0 ; j <= C ; j ++)
            memo[0][j] = (j >= w[0] ? v[0] : 0);

        for(int i = 1 ; i < n ; i ++)
            for(int j = 0 ; j <= C ; j ++){
                memo[i % 2][j] = memo[(i-1) % 2][j];
                if(j >= w[i])
                    memo[i % 2][j] = Math.max(memo[i % 2][j], v[i] + memo[(i-1) % 2][j - w[i]]);
            }

        return memo[(n-1) % 2][C];
    }

    public static void main(String[] args) {    }
}

/// 背包問題
/// 動态規劃改進
/// 時間複雜度: O(n * C) 其中n為物品個數; C為背包容積
/// 空間複雜度: O(C), 隻使用了C的額外空間
public class Solution2 {

    public int knapsack01(int[] w, int[] v, int C){

        if(w == null || v == null || w.length != v.length)
            throw new IllegalArgumentException("Invalid w or v");

        if(C < 0)
            throw new IllegalArgumentException("C must be greater or equal to zero.");

        int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        int[] memo = new int[C+1];

        for(int j = 0 ; j <= C ; j ++)
            memo[j] = (j >= w[0] ? v[0] : 0);

        for(int i = 1 ; i < n ; i ++)
            for(int j = C ; j >= w[i] ; j --)
                memo[j] = Math.max(memo[j], v[i] + memo[j - w[i]]);

        return memo[C];
    }

    public static void main(String[] args) {

    }
}

0-1背包問題更多變種

完全背包問題：每個物品可以無限使用

多重背包問題：每個物品不止1個，有num[i]個

多元費用背包問題：要考慮物品的體積和重量兩個次元

物品間加入更多限制：物品間可以互相排斥、也可以互相依賴

9-7 面試中的0-1背包問題 Partition Equal Subset Sum

題目: LeetCode 416. 分割等和子集

給定一個隻包含正整數的非空數組。是否可以将這個數組分割成兩個子集，使得兩個子集的元素和相等。

注意:

每個數組中的元素不會超過 100

數組的大小不會超過 200

示例 1:

輸入: [1, 5, 11, 5]

輸出: true

解釋: 數組可以分割成 [1, 5, 5] 和 [11].

示例 2:

輸入: [1, 2, 3, 5]

輸出: false

解釋: 數組不能分割成兩個元素和相等的子集.典型的背包問題，在n個物品中選出一定物品，填滿sum/2的背包。

其中對“狀态”的定義：F(n, c)考慮将n個物品填滿容量為c的背包。

根據對狀态的定義，決定狀态的轉移：

F(i, c) = F(i - 1, c) || F(i-1, c - w(i))

import java.util.Arrays;

/// 416. Partition Equal Subset Sum
/// https://leetcode.com/problems/partition-equal-subset-sum/description/
/// 記憶化搜尋
/// 時間複雜度: O(len(nums) * O(sum(nums)))
/// 空間複雜度: O(len(nums) * O(sum(nums)))
public class Solution1 {

    // memo[i][c] 表示使用索引為[0...i]的這些元素,是否可以完全填充一個容量為c的背包
    // -1 表示為未計算; 0 表示不可以填充; 1 表示可以填充
    private int[][] memo;

    public boolean canPartition(int[] nums) {

        int sum = 0;
        for(int i = 0 ; i < nums.length ; i ++){
            if(nums[i] <= 0)
                throw new IllegalArgumentException("numbers in nums must be greater than zero.");
            sum += nums[i];
        }

        if(sum % 2 == 1)
            return false;

        memo = new int[nums.length][sum / 2 + 1];
        for(int i = 0 ; i < nums.length ; i ++)
            Arrays.fill(memo[i], -1);
        return tryPartition(nums, nums.length - 1, sum / 2);
    }

    // 使用nums[0...index], 是否可以完全填充一個容量為sum的背包
    private boolean tryPartition(int[] nums, int index, int sum){

        if(sum == 0)
            return true;

        if(sum < 0 || index < 0)
            return false;

        if(memo[index][sum] != -1)
            return memo[index][sum] == 1;

        memo[index][sum] = (tryPartition(nums, index - 1, sum) ||
                tryPartition(nums, index - 1, sum - nums[index])) ? 1 : 0;

        return memo[index][sum] == 1;
    }

    private static void printBool(boolean res){
        System.out.println(res ? "True" : "False");
    }

    public static void main(String[] args) {

        int[] nums1 = {1, 5, 11, 5};
        printBool((new Solution1()).canPartition(nums1));        int[] nums2 = {1, 2, 3, 5};
        printBool((new Solution1()).canPartition(nums2));
    }
}

import java.util.Arrays;

/// 416. Partition Equal Subset Sum
/// https://leetcode.com/problems/partition-equal-subset-sum/description/
/// 動态規劃
/// 時間複雜度: O(len(nums) * O(sum(nums)))
/// 空間複雜度: O(len(nums) * O(sum(nums)))
public class Solution2 {

    public boolean canPartition(int[] nums) {

        int sum = 0;
        for(int i = 0 ; i < nums.length ; i ++){
            if(nums[i] <= 0)
                throw new IllegalArgumentException("numbers in nums must be greater than zero.");
            sum += nums[i];
        }

        if(sum % 2 == 1)
            return false;

        int n = nums.length;
        int C = sum / 2;

        boolean[] memo = new boolean[C + 1];
        for(int i = 0 ; i <= C ; i ++)
            memo[i] = (nums[0] == i);

        for(int i = 1 ; i < n ; i ++)
            for(int j = C; j >= nums[i] ; j --)
                memo[j] = memo[j] || memo[j - nums[i]];

        return memo[C];
    }

    private static void printBool(boolean res){
        System.out.println(res ? "True" : "False");
    }

    public static void main(String[] args) {

        int[] nums1 = {1, 5, 11, 5};
        printBool((new Solution2()).canPartition(nums1));

        int[] nums2 = {1, 2, 3, 5};
        printBool((new Solution2()).canPartition(nums2));
    }
}

課後作業: LeetCode 322、377、474、139、494

9-8 LIS問題 Longest Increasing Subsequence

題目: LeetCode 300. 最長上升子序列

給定一個無序的整數數組，找到其中最長上升子序列的長度。

示例:

輸入: [10,9,2,5,3,7,101,18]

輸出: 4

解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。

說明:

可能會有多種最長上升子序列的組合，你隻需要輸出對應的長度即可。

你算法的時間複雜度應該為 O(n2) 。

進階: 你能将算法的時間複雜度降低到 O(n log n) 嗎?暴力解法：選擇所有的子序列進行判斷。

動态規劃：

其中對“狀态”的定義：LIS(i)表示以第i個數字為結尾的最長上升子序列的長度。即LIS(i)表示[0,…,i]的範圍内，選擇數字nums[i]可以獲得的最長上升子序列的長度。

根據對狀态的定義，決定狀态的轉移：

LIS(i) = 當(j < i)時，max{1 + LIS(j) if nums[i] > nums[j]}

import java.util.Arrays;

/// 300. Longest Increasing Subsequence
/// https://leetcode.com/problems/longest-increasing-subsequence/description/
/// 記憶化搜尋
/// 時間複雜度: O(n^2)
/// 空間複雜度: O(n)
public class Solution1 {

    private int[] memo;

    public int lengthOfLIS(int[] nums) {

        if(nums.length == 0)
            return 0;

        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        int res = 1;
        for(int i = 0 ; i < nums.length ; i ++)
            res = Math.max(res, getMaxLength(nums, i));

        return res;
    }

    // 以 nums[index] 為結尾的最長上升子序列的長度
    private int getMaxLength(int[] nums, int index){

        if(memo[index] != -1)
            return memo[index];

        int res = 1;
        for(int i = 0 ; i <= index-1 ; i ++)
            if(nums[index] > nums[i])
                res = Math.max(res, 1 + getMaxLength(nums, i));

        return memo[index] = res;
    }

    public static void main(String[] args) {

        int nums1[] = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println((new Solution1()).lengthOfLIS(nums1));
        // 4

        // ---

        int nums2[] = {4, 10, 4, 3, 8, 9};
        System.out.println((new Solution1()).lengthOfLIS(nums2));
        // 3

        // ---

        int nums3[] = {2, 2};
        System.out.println((new Solution1()).lengthOfLIS(nums3));
        // 1

        // ---        int nums4[] = {1, 3, 6, 7, 9, 4, 10, 5, 6};
        System.out.println((new Solution1()).lengthOfLIS(nums4));
        // 6
    }
}

import java.util.Arrays;

/// 300. Longest Increasing Subsequence
/// https://leetcode.com/problems/longest-increasing-subsequence/description/
/// 記憶化搜尋
/// 時間複雜度: O(n^2)
/// 空間複雜度: O(n)
public class Solution2 {

    public int lengthOfLIS(int[] nums) {

        if(nums.length == 0)
            return 0;

        // memo[i] 表示以 nums[i] 為結尾的最長上升子序列的長度
        int memo[] = new int[nums.length];
        Arrays.fill(memo, 1);
        for(int i = 1 ; i < nums.length ; i ++)
            for(int j = 0 ; j < i ; j ++)
                if(nums[i] > nums[j])
                    memo[i] = Math.max(memo[i], 1 + memo[j]);

        int res = memo[0];
        for(int i = 1 ; i < nums.length ; i ++)
            res = Math.max(res, memo[i]);

        return res;
    }

    public static void main(String[] args) {

        int nums1[] = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println((new Solution2()).lengthOfLIS(nums1));
        // 4

        // ---

        int nums2[] = {4, 10, 4, 3, 8, 9};
        System.out.println((new Solution2()).lengthOfLIS(nums2));
        // 3

        // ---

        int nums3[] = {2, 2};
        System.out.println((new Solution2()).lengthOfLIS(nums3));
        // 1

        // ---

        int nums4[] = {1, 3, 6, 7, 9, 4, 10, 5, 6};
        System.out.println((new Solution2()).lengthOfLIS(nums4));
        // 6
    }
}

課後作業: LeetCode 376

9-9 LCS，最短路，求動态規劃的具體解以及更多

題目: LCS （最長公共子序列）。LCS是Longest Common Subsequence的縮寫，即最長公共子序列。一個序列，如果是兩個或多個已知序列的子序列，且是所有子序列中最長的，則為最長公共子序列。

比如，對于char x[]=“aabcd”;有順序且互相相鄰的aabc是其子序列，有順序但是不相鄰的abc也是其公共子序列。即，隻要得出序列中各個元素屬于所給出的數列，就是子序列。

再加上char y[]=“12abcabcd”;對比出才可以得出最長公共子序列abcd。

動态規劃：

其中對“狀态”的定義：LCS(m, n)表示s1[0,…,m]和s2[0,…,n]的最長公共子序列的長度。

根據對狀态的定義，決定狀态的轉移：

s1[m] == s2[n]: LCS(m, n) = 1 + LCS(m - 1, n - 1)

s1[m] != s2[n]: LCS(m, n) = max{LCS(m - 1, n), LCS(m, n - 1)}

import java.util.Arrays;

/// LCS問題
/// 動态規劃
/// 時間複雜度: O(len(s1)*len(s2))
/// 空間複雜度: O(len(s1)*len(s2))
public class LCS1 {

    private int[][] memo;

    public String lcs(String s1, String s2){

        if(s1 == null || s2 == null)
            throw new IllegalArgumentException("s1 and s2 can not be null.");

        if(s1.length() == 0 || s2.length() == 0)
            return "";

        memo = new int[s1.length()][s2.length()];
        for(int i = 0 ; i < s1.length() ; i ++)
            Arrays.fill(memo[i], -1);

        lcs(s1, s2, s1.length() - 1, s2.length() - 1);
        return getLCS(s1, s2);
    }

    // 求s1[0...m]和s2[0...n]的最長公共子序列的長度值
    private int lcs(String s1, String s2, int m, int n){

        if(m < 0 || n < 0)
            return 0;

        if(memo[m][n] != -1)
            return memo[m][n];

        int res = 0;
        if(s1.charAt(m) == s2.charAt(n))
            res = 1 + lcs(s1, s2, m - 1, n - 1);
        else
            res = Math.max(lcs(s1, s2, m - 1, n),
                           lcs(s1, s2, m, n - 1));

        memo[m][n] = res;
        return res;
    }

    // 通過memo反向求解s1和s2的最長公共子序列
    private String getLCS(String s1, String s2){

        int m = s1.length() - 1;
        int n = s2.length() - 1;

        StringBuilder res = new StringBuilder("");
        while(m >= 0 && n >= 0)
            if(s1.charAt(m) == s2.charAt(n)){
                res = res.insert(0, s1.charAt(m));
                m --;
                n --;
            }
            else if(m == 0)
                n --;
            else if(n == 0)
                m --;
            else{
                if(memo[m-1][n] > memo[m][n-1])
                    m --;
                else
                    n --;
            }

        return res.toString();
    }

    public static void main(String[] args) {

        String s1 = "ABCDGH";
        String s2 = "AEDFHR";
        System.out.println((new LCS1()).lcs(s1, s2));        s1 = "AAACCGTGAGTTATTCGTTCTAGAA";
        s2 = "CACCCCTAAGGTACCTTTGGTTC";
        System.out.println((new LCS1()).lcs(s1, s2));
    }
}

/// LCS問題
/// 動态規劃
/// 時間複雜度: O(len(s1)*len(s2))
/// 空間複雜度: O(len(s1)*len(s2))
public class LCS2 {

    public String lcs(String s1, String s2){

        int m = s1.length();
        int n = s2.length();

        // 對memo的第0行和第0列進行初始化
        int[][] memo = new int[m][n];
        for(int j = 0 ; j < n ; j ++)
            if(s1.charAt(0) == s2.charAt(j)){
                for(int k = j ; k < n ; k ++)
                    memo[0][k] = 1;
                break;
            }

        for(int i = 0 ; i < m ; i ++)
            if(s1.charAt(i) == s2.charAt(0)) {
                for(int k = i ; k < m ; k ++)
                    memo[k][0] = 1;
                break;
            }

        // 動态規劃的過程
        for(int i = 1 ; i < m ; i ++)
            for(int j = 1 ; j < n ; j ++)
                if(s1.charAt(i) == s2.charAt(j))
                    memo[i][j] = 1 + memo[i-1][j-1];
                else
                    memo[i][j] = Math.max(memo[i-1][j], memo[i][j-1]);

        // 通過memo反向求解s1和s2的最長公共子序列
        m = s1.length() - 1;
        n = s2.length() - 1;
        StringBuilder res = new StringBuilder("");
        while(m >= 0 && n >= 0)
            if(s1.charAt(m) == s2.charAt(n)){
                res.insert(0, s1.charAt(m));
                m --;
                n --;
            }
            else if(m == 0)
                n --;
            else if(n == 0)
                m --;
            else{
                if(memo[m-1][n] > memo[m][n-1])
                    m --;
                else
                    n --;
            }

        return res.toString();
    }

    public static void main(String[] args) {

        String s1 = "ABCDGH";
        String s2 = "AEDFHR";
        System.out.println((new LCS2()).lcs(s1, s2));

        s1 = "AAACCGTGAGTTATTCGTTCTAGAA";
        s2 = "CACCCCTAAGGTACCTTTGGTTC";
        System.out.println((new LCS2()).lcs(s1, s2));
    }
}

/// LCS問題
/// 動态規劃, 躲避邊界條件
/// 時間複雜度: O(len(s1)*len(s2))
/// 空間複雜度: O(len(s1)*len(s2))
public class LCS3 {

    public String lcs(String s1, String s2){

        int m = s1.length();
        int n = s2.length();

        // memo 是 (m + 1) * (n + 1) 的動态規劃表格
        // memo[i][j] 表示s1的前i個字元和s2前j個字元的最長公共子序列的長度
        // 其中memo[0][j] 表示s1取空字元串時, 和s2的前j個字元作比較
        // memo[i][0] 表示s2取空字元串時, 和s1的前i個字元作比較
        // 是以, memo[0][j] 和 memo[i][0] 均取0
        // 我們不需要對memo進行單獨的邊界條件處理 :-)
        int[][] memo = new int[m + 1][n + 1];

        // 動态規劃的過程
        // 注意, 由于動态規劃狀态的轉變, 下面的i和j可以取到m和n
        for(int i = 1 ; i <= m ; i ++)
            for(int j = 1 ; j <= n ; j ++)
                if(s1.charAt(i - 1) == s2.charAt(j - 1))
                    memo[i][j] = 1 + memo[i - 1][j - 1];
                else
                    memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);

        // 通過memo反向求解s1和s2的最長公共子序列
        m = s1.length();
        n = s2.length();
        StringBuilder res = new StringBuilder("");
        while(m > 0 && n > 0)
            if(s1.charAt(m - 1) == s2.charAt(n - 1)){
                res.insert(0, s1.charAt(m - 1));
                m --;
                n --;
            }
            else if(memo[m - 1][n] > memo[m][n - 1])
                m --;
            else
                n --;

        return res.toString();
    }

    public static void main(String[] args) {

        String s1 = "ABCDGH";
        String s2 = "AEDFHR";
        System.out.println((new LCS3()).lcs(s1, s2));

        s1 = "AAACCGTGAGTTATTCGTTCTAGAA";
        s2 = "CACCCCTAAGGTACCTTTGGTTC";
        System.out.println((new LCS3()).lcs(s1, s2));
    }
}

第9章動态規劃基礎