#動(dòng)態(tài)規(guī)劃#
動(dòng)態(tài)規(guī)劃特點(diǎn)：

• 把原始問題劃分成一系列子問題；
• 求解每個(gè)子問題僅一次，并將其結(jié)果保存在一個(gè)表中，以后用到時(shí)直接存取，不重復(fù)計(jì)算，節(jié)省計(jì)算時(shí)間
• 自底向上地計(jì)算。（base case）
• 整體問題最優(yōu)解取決于子問題的最優(yōu)解（狀態(tài)轉(zhuǎn)移方程）（將子問題稱為狀態(tài)，最終狀態(tài)的求解歸結(jié)為其他狀態(tài)的求解）

300. 最長(zhǎng)遞增子序列

問題描述

給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。
子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

解題思路

問題拆分：首先，求出以數(shù)組中的每個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度；然后取其中的最大值
base case：數(shù)組中僅有一個(gè)元素時(shí)，唯一的子序列是nums[0]，所以最長(zhǎng)遞增子序列長(zhǎng)度為1
狀態(tài)轉(zhuǎn)移：以nums[i]結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度= 在nums[i]之前的以小于nums[i]的數(shù)結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度中的最大值 + 1

代碼實(shí)現(xiàn)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if(len == 0){
            return 0;
        }

        //定義dp數(shù)組: dp[i]表示以nums[i]結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度
        int[] dp = new int[len];
        //以nums[0]結(jié)尾的最長(zhǎng)子序列只有它自己
        dp[0] = 1;

        for(int i = 0; i < len; i++){
            //以nums[i]結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度= nums[i]之前的以小于nums[i]的數(shù)結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度中的最大值 + 1
            int max = 0;
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i] && max < dp[j]){
                    max = dp[j];
                }
            }
            dp[i] = max + 1; 
        }

        //返回dp數(shù)組中的最大值
        int res = 0;
        for(int n : dp){
            if(res < n){
                res = n;
            }
        }
        return res;

    }
}

• 時(shí)間復(fù)雜度:O(n^2)，n為數(shù)組中的元素
• 空間復(fù)雜度：O(n)，使用長(zhǎng)度為 n的 dp數(shù)組保存子問題結(jié)果

152. 乘積最大子數(shù)組

問題描述

給你一個(gè)整數(shù)數(shù)組 nums ，請(qǐng)你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個(gè)數(shù)字），并返回該子數(shù)組所對(duì)應(yīng)的乘積。

解題思路

由于此題數(shù)組中的元素既可能是正數(shù)（與正數(shù)相乘的數(shù)越大得到的乘積越大），也可能為負(fù)數(shù)（與負(fù)數(shù)的數(shù)越小得到的乘積才越大）
因此維護(hù)一個(gè)二維的dp數(shù)組存儲(chǔ)以nums[i]結(jié)尾的最大/最小連續(xù)子數(shù)組乘積；

代碼實(shí)現(xiàn)1-動(dòng)態(tài)規(guī)劃

class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        if(len == 0){
            return 0;
        }
        //dp[i][0]表示以nums[i]結(jié)尾的最小連續(xù)子數(shù)組乘積
        //dp[i][1]表示以nums[i]結(jié)尾的最大連續(xù)子數(shù)組乘積
        int[][] dp = new int[len][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];

        int max = nums[0];

        for(int i = 1; i < len; i++){
             int minP = nums[i] * dp[i-1][0];
             int maxP = nums[i] * dp[i-1][1];

             dp[i][0] = Math.min(Math.min(minP,maxP),nums[i]);
             dp[i][1] = Math.max(Math.max(minP,maxP),nums[i]);

             //更新最值
             max = Math.max(max, dp[i][1]);      
        }

        return max;
    }
}

• 時(shí)間復(fù)雜度：O(n)，n為數(shù)組中的元素
• 空間復(fù)雜度：O(n)，n為數(shù)組中的元素
  上面的代碼，在狀態(tài)轉(zhuǎn)移時(shí)，dp[i]只與dp[i-1]相關(guān)，因此，可以進(jìn)行“狀態(tài)壓縮”，用變量來代替dp數(shù)組，降低空間復(fù)雜度。

代碼實(shí)現(xiàn)-壓縮空間

class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        if(len == 0){
            return 0;
        }   
        int dpMin = nums[0], dpMax = nums[0], max = nums[0];
        for(int i = 1; i < len; i++){
             int minP = nums[i] * dpMin;
             int maxP = nums[i] * dpMax;
             dpMin = Math.min(Math.min(minP,maxP),nums[i]);
             dpMax = Math.max(Math.max(minP,maxP),nums[i]);
             max = Math.max(max,dpMax);  
        }
        return max;
    }
}

參考資料：【算法復(fù)習(xí)】動(dòng)態(tài)規(guī)劃