感覺就分幾種類型：

第1種：連續(xù)求和類型（只用dp[i-1]）

題目：53. 最大子序和

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

代碼：

class Solution {
    public int maxSubArray(int[] nums) {
        int ans=nums[0];
        int dp=0;
        for(int num:nums){
            dp=Math.max(dp+num,num);
            ans=Math.max(ans,dp);
        }
        return ans;
    }
}

狀態(tài)轉(zhuǎn)換：

用記事本記下以該位置為結(jié)尾的最大子序列和，然后比較選出最大子序列和

與此相同的題目有
題目：面試題42. 連續(xù)子數(shù)組的最大和

輸入一個整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中的一個或連續(xù)多個整數(shù)組成一個子數(shù)組。求所有子數(shù)組的和的最大值。

要求時間復(fù)雜度為O(n)。

示例1:

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

第2種：斐波那契數(shù)列類型 （只用dp[i-1]和dp[i-2]）

題目 70. 爬樓梯

70.爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

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

注意：給定 n 是一個正整數(shù)。

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階
   示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

代碼：

class Solution {
    public int climbStairs(int n) {
        if(n==1)return 1;
        if(n==2)return 2;
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        
        for(int i = 3 ; i <= n ; i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

題目：面試題 08.01. 三步問題

三步問題。有個小孩正在上樓梯，樓梯有n階臺階，小孩一次可以上1階、2階或3階。實(shí)現(xiàn)一種方法，計算小孩有多少種上樓梯的方式。結(jié)果可能很大，你需要對結(jié)果模1000000007。

示例1:

輸入：n = 3
輸出：4
說明: 有四種走法
示例2:

輸入：n = 5
輸出：13
提示:

n范圍在[1, 1000000]之間

代碼：

class Solution {
    public int waysToStep(int n) {
        int[] dp=new int[n+1];
        switch(n){
            case 1:return 1;
            case 2:return 2;
            case 3:return 4;
        }
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i = 4; i< n+1;i++){
            dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;
        }
        return dp[n];
    }
}

題目：面試題 17.16. 按摩師

一個有名的按摩師會收到源源不斷的預(yù)約請求，每個預(yù)約都可以選擇接或不接。在每次預(yù)約服務(wù)之間要有休息時間，因此她不能接受相鄰的預(yù)約。給定一個預(yù)約請求序列，替按摩師找到最優(yōu)的預(yù)約集合（總預(yù)約時間最長），返回總的分鐘數(shù)。

注意：本題相對原題稍作改動

示例 1：

輸入： [1,2,3,1]
輸出： 4
解釋： 選擇 1 號預(yù)約和 3 號預(yù)約，總時長 = 1 + 3 = 4。
示例 2：

輸入： [2,7,9,3,1]
輸出： 12
解釋： 選擇 1 號預(yù)約、 3 號預(yù)約和 5 號預(yù)約，總時長 = 2 + 9 + 1 = 12。
示例 3：

輸入： [2,1,4,5,3,1,1,3]
輸出： 12
解釋： 選擇 1 號預(yù)約、 3 號預(yù)約、 5 號預(yù)約和 8 號預(yù)約，總時長 = 2 + 4 + 3 + 3 = 12。

代碼：

class Solution {
    public int massage(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        int[] dp= new int[3];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i = 2; i < nums.length; i++){
            dp[i%3]=Math.max(dp[(i-2)%3]+nums[i],dp[(i-1)%3]);
        }
        return dp[(nums.length-1)%3];
    }
}

利用取余降低空間復(fù)雜度。
題目：198. 打家劫舍

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

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

示例 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 。

代碼：

class Solution {
    public int rob(int[] nums) {
        
        int len = nums.length;
        if(len==0)return 0;
        if(len==1)return nums[0];
        int[] dp=new int[3];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i = 2; i <len; i++){
            dp[i%3]=Math.max(dp[(i-1)%3],dp[(i-2)%3]+nums[i]);
        }
        return dp[(len-1)%3];
    }
}

題目：746. 使用最小花費(fèi)爬樓梯

數(shù)組的每個索引做為一個階梯，第 i個階梯對應(yīng)著一個非負(fù)數(shù)的體力花費(fèi)值 costi。

每當(dāng)你爬上一個階梯你都要花費(fèi)對應(yīng)的體力花費(fèi)值，然后你可以選擇繼續(xù)爬一個階梯或者爬兩個階梯。

您需要找到達(dá)到樓層頂部的最低花費(fèi)。在開始時，你可以選擇從索引為 0 或 1 的元素作為初始階梯。

示例 1:

輸入: cost = [10, 15, 20]
輸出: 15
解釋: 最低花費(fèi)是從cost[1]開始，然后走兩步即可到階梯頂，一共花費(fèi)15。
示例 2:

輸入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出: 6
解釋: 最低花費(fèi)方式是從cost[0]開始，逐個經(jīng)過那些1，跳過cost[3]，一共花費(fèi)6。
注意：

cost 的長度將會在 [2, 1000]。
每一個 cost[i] 將會是一個Integer類型，范圍為 [0, 999]。

代碼：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len];
        dp[0]=0;
        dp[1]=Math.min(cost[0],cost[1]);
        for(int i = 2; i < len; i++){
            dp[i]=Math.min(dp[i-1]+cost[i],dp[i-2]+cost[i-1]);
        }
        return dp[len-1];

    }
}

總結(jié)：只是利用本子把前兩個數(shù)記下來

第3種簡單狀態(tài)轉(zhuǎn)換公式（用一維數(shù)組dp[N+1]記錄前后之間關(guān)系）

題目：303. 區(qū)域和檢索 - 數(shù)組不可變

給定一個整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j (i ≤ j) 范圍內(nèi)元素的總和，包含 i, j 兩點(diǎn)。

示例：

給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數(shù)為 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
說明:

你可以假設(shè)數(shù)組不可變。
會多次調(diào)用 sumRange 方法。

代碼：

class NumArray {
    int[] nums=null;
    int sum=0;
    int[] dp=null;
    public NumArray(int[] nums) {
        this.nums=nums;
        int[] dp=new int[nums.length+1];
        dp[0]=0;
        for(int i = 1 ; i< nums.length+1;i++){
            sum+=nums[i-1];
            dp[i]=sum;
        }
        this.dp=dp;
    }
    
    public int sumRange(int i, int j) {
        return (dp[j+1]-dp[i]);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

記事本簡單記的是true或false（Y or N)
根據(jù)上一步的結(jié)果來判斷下一步操作。
題目：1025. 除數(shù)博弈

愛麗絲和鮑勃一起玩游戲，他們輪流行動。愛麗絲先手開局。

最初，黑板上有一個數(shù)字 N 。在每個玩家的回合，玩家需要執(zhí)行以下操作：

選出任一 x，滿足 0 < x < N 且 N % x == 0 。
用 N - x 替換黑板上的數(shù)字 N 。
如果玩家無法執(zhí)行這些操作，就會輸?shù)粲螒颉?/p>

只有在愛麗絲在游戲中取得勝利時才返回 True，否則返回 false。假設(shè)兩個玩家都以最佳狀態(tài)參與游戲。

示例 1：

輸入：2
輸出：true
解釋：愛麗絲選擇 1，鮑勃無法進(jìn)行操作。
示例 2：

輸入：3
輸出：false
解釋：愛麗絲選擇 1，鮑勃也選擇 1，然后愛麗絲無法進(jìn)行操作。

提示：

1 <= N <= 1000

代碼：

class Solution {
    public boolean divisorGame(int N) {
       
        if(N==1)return false;
        int[] dp=new int[N+1];
        dp[1]=0;
        dp[2]=1;
        for(int i = 3; i <N+1;i++){
            for(int j = 1; j<i; j++){
                if(i%j==0&&dp[i-j]==0){
                    dp[i]=1;
                    break;
                }
            }
        }
        return dp[N]==1;
    }
}

外循環(huán)是記事本，內(nèi)循環(huán)是過往的記事本，只要翻舊賬能翻出符合條件的就把今天的事情翻篇。

第四種類型 兩個對象比較 （用二維數(shù)組dp[M+1][N+1]表示之間的關(guān)系）

題目：392. 判斷子序列

給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

你可以認(rèn)為 s 和 t 中僅包含英文小寫字母。字符串 t 可能會很長（長度 ~= 500,000），而 s 是個短字符串（長度 <=100）。

字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

后續(xù)挑戰(zhàn) :

如果有大量輸入的 S，稱作S1, S2, ... , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會怎樣改變代碼？

代碼：

class Solution {
    public boolean isSubsequence(String s, String t) {
        int  slen=s.length();
        int  tlen=t.length();
        int[][] dp=new int[slen+1][tlen+1];
        if(slen==0){
            return true;
        }
        if(tlen==0){
            return false;
        }
        for(int i = 0; i <tlen; i++){
            dp[0][i]=1;
        }
        for(int i = 1 ; i <=slen; i++){
            for(int j = 1 ; j <=tlen; j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=dp[i][j-1];
                }
            }
        }
        return dp[slen][tlen]==1;
    }
}

當(dāng)char[i]==char[j]時，則字符i一定是j的子序列，如果0 ~ i - 1 子字符串是0 ~ j - 1子字符串的子序列，則dp[i][j]=true，所以dp[i][j] = dp[i-1][j-1]；承接上一個狀態(tài)；
當(dāng)char[i]!=char[i]時，即判斷當(dāng)前0_{i子字符串是否是0}j-1的子字符串的子序列，dp[i][j]=dp[i][j-1]; 承接上一個狀態(tài)