class Solution {
    public int tribonacci(int n) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        // 处理边界情况
        if (n == 0)
            return 0;

        if (n == 1 || n == 2)
            return 1;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = dp[2] = 1;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        return dp[n];
    }
}

// 空间优化写法：
class Solution {
    public int tribonacci(int n) {
        // 可以递归写，也可以使用动态规划
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 1;
        int ret = 0;
        int a = 0, b = 1, c = 1;
        for(int i=0;i<n-2;i++){
            ret = a+b+c;
            a=b;
            b=c;
            c=ret;
        }
        return c;
    }
}

class Solution {
    public int tribonacci(int n) {
        // 可以递归写，也可以使用动态规划
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 1;
        return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);
    }
}

**状态表示：**dp[i]表示第i个泰波纳契数列的值。
**状态转移方程：**dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
**初始化：**因为前三个值是固定的，所以直接给dp[0]、dp[1]、dp[2]赋值即可。
**填表顺序：**从左向右填表。
**返回结果：**dp[n]。

**思考：**动态规划的思想和递归有相似之处，都是通过规模更小的子问题来得出问题的答案
动态规划的步骤：

1. 定义状态表示，创建dp表。（这个需要经验，具体问题具体分析）
2. 初始化dp表，该题根据题目意思进行初始化
3. 填表，需要注意填表顺序
4. 返回结果，根据题目意思来判断，有时候是dp表的最后一个值，有时候是dp表求和或者最值。

class Solution {
    public int waysToStep(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        int MOD = 1000000007;// 十亿
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i=4;i<=n;i++){
            // 状态转移方程：
            dp[i] = ((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;
        }
        return dp[n];
    }
}

PS:因为两个数相加有可能大于MOD，所以要每两个数相加都进行模MOD
**状态表示：**dp[i]表示走到第i个台阶有dp[i]种上楼梯的方式
**状态转移方程：**dp[i] = ((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;
**初始化：**由题意可知，前几个值可以直接填写。
**填表顺序：**从左向右填表。
**返回结果：**dp[n]。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 爬出数组操作是爬到楼梯顶
        int n = cost.length;
        // dp[i]:爬到第i层的最小花费，dp[n]就是爬到顶部的最小花费
        int[] dp = new int[n+1];
        // dp初始化
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<=n;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
}

分析问题 —> 状态转移方程 —> dp表创建以及初始化 —> 填写dp表
**状态表示：**dp[i]:爬到第i层的最小花费，dp[n]就是爬到顶部的最小花费
**状态转移方程：**dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);爬到第i个台阶有两种方式，去两种方式花费的最小值。
**初始化：**由题意可知，前几个值可以直接填写。
**填表顺序：**从左向右填表。
**返回结果：**dp[n]。

class Solution {
    public int numDecodings(String s) {
        // 存在前导0时无法解码，直接返回0
        if(s.charAt(0)=='0') return 0;
        int n = s.length();
        // 0、定义状态表示，dp[i]表示以i位置为结尾的子串有多少种解码方式
        // 之所以数组大小定义为n+1,是为了填表的时候防止越界访问
        int[] dp = new int[n + 1];
        // dp[0]表示空串的解码方式有多少种，初始值应该为0或用0-1表示没有意义。但是为了后续填表的正确性dp[0]应该初始化为1.也就是说此处的初始化并没有实际意义，仅仅只是为了填表方便
        
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 当前字符 cur,前置字符 pre
            int pre = s.charAt(i-2)-'0';
            int cur = s.charAt(i-1)-'0';
            // 如果pre和cur组成的数字可以解码
            if(10<=(pre*10+cur) && (pre*10+cur)<=26){
                dp[i] += dp[i - 2];
            }
            // 单独的cur进行解码
            if(1<=cur&&cur<=9){
                dp[i] += dp[i - 1];
            }
            // 非法情况直接返回0
            if(cur==0 && (pre==0||pre>2)){
                return 0;
            }
        }
        return dp[n];
    }
}

这个课是听过一遍的，写起来还算有点记忆。
**状态表示：**dp[i]表示以i位置为结尾的子串有多少种解码方式。
**初始化：**dp[0]表示空串的解码方式有多少种，初始值应该为0或用0-1表示没有意义。但是为了后续填表的正确性dp[0]应该初始化为1.也就是说此处的初始化并没有实际意义，仅仅只是为了填表方便。
**填表顺序：**从左向右
**返回值：**dp[n].

class Solution {
    public int uniquePaths(int m, int n) {
        // 这是一个排列组合的问题，有公式可以直接秒。
        // 动态规划解法：
        int[][] dp = new int[m+1][n+1];
        // 为什么要这么进行初始化？
        dp[0][1] = 1;
        // 填表顺序：从上到小，从左到右
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                // 想要走到[i,j]位置，有两种方式，有x中方式走到[i-1,j],有y种方式走到[i,j-1]
                // 那么走到[i,j]的方式就有x+y种。
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];

    }
}

由题意可知，初始化应为：dp[i][1]=dp[1][j]=1。为了编码简单我们创建的dp表比原数组长度大1，
dp[i][1]和dp[1][j]都应该等于1，dp[1][1] = dp[1][0] + dp[0][1];所以仅需将dp[1][0]或者dp[0][1]设置为1即可。

动态规划的核心就是：

1. 明确dp表的含义；
2. 确定状态转移方程

细节问题：

1. dp表是一维的还是二维的？
2. dp表的大小（一般是要比原数组长度大1）
3. 如何初始化

初始化的几种情况：1、具有实际意义。2、编码需要，为填表工作服务。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m+1][n+1];
        // 为什么要这么进行初始化？为了dp[1][1]位置填表的正确性。！！
        dp[0][1] = 1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(obstacleGrid[i-1][j-1]==1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
}

路径上存在障碍物，多加一层判断即可。
为什么要初始化dp[0][1]=1？为了dp[1][1]位置填表的正确性。

class Solution {
    public int jewelleryValue(int[][] frame) {
        // 从左上角到右下角的路径和最大值
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                // 填表规则，两种方式取较大的哪一种
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}

dp[i][j]表示从起点到达[i,j]位置珠宝总价值的最大值。
所以有状态转移方程：dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 0、如果建一个更大的dp表，在填充dp表的时候就不需要考虑数组越界的问题了
        int[][] dp = new int[m+1][n+2];
        // 1、初始化，周围一圈需要初始化为无穷大
        for(int i=1;i<m+1;i++){
            dp[i][0]=Integer.MAX_VALUE;
            dp[i][n+1]=Integer.MAX_VALUE;
        }
        // 2、填写dp表 
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                int min = Math.min(dp[i-1][j-1],dp[i-1][j]);
                min = Math.min(min,dp[i-1][j+1]);
                dp[i][j] = matrix[i-1][j-1] + min;
            }
        }
        // 3、找最后一行的最小值
        int min = dp[m][n];
        for(int i=1;i<=n-1;i++){
            min = Math.min(min,dp[m][i]);
        }
        return min;  
    }
}

图示：

**状态表示：**dp[i][j]表示下降到[i,j]位置时的最小值，因此返回值应该是最下面一行的最小值
**初始化：**dp建的比较大是为了填表时的越界访问，但是数组的默认值会干扰填表，根据题目意思将数组的第一列和最后一列设置为一个大数即可。
**填表顺序：**从上到下，同一行中填顺序无所谓
**返回值：**最后一行的最小值。

class Solution {
    public int minPathSum(int[][] grid) {
        // 从左上角到右下角的路径和最大值
        int m = grid.length;
        int n = grid[0].length;
        // dp表建的比较大是为了防止数组越界，省去判断下标合法。
        int[][] dp = new int[m+1][n+1];
        // 为了防止dp边界值影响dp的填充，所以要做初始化
        
        for(int i=0;i<=m;i++) dp[i][0] = Integer.MAX_VALUE;
        for(int i=0;i<=n;i++) dp[0][i] = Integer.MAX_VALUE;
        dp[0][1] = dp[1][0] = 0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}

图示：

dp表创建的大一点是为了避免填表时越界访问，
为了防止dp边界值影响dp的填充，所以要做初始化

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        // 0、创建dp表
        int[][] dp = new int[m+1][n+1];

        // 1、初始化dp表
        for(int i=0;i<m;i++)
            dp[i][n] = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            dp[m][i] = Integer.MAX_VALUE;
        }
        dp[m-1][n] = dp[m][n-1] = 1;

        // 2、填充dp表,正难则反
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                // 从dp[i][j]去往dp[i+1][j]或者dp[i][j+1]，选择两者较小的哪一个
                int min = Math.min(dp[i+1][j],dp[i][j+1]);
                // 如果该房间可以增加健康值，且dungeon[i][j]>=min，
                // 那么从进入这个房间并到达终点所需要的能量为1，因为保持能量为正才能进入房间
                if(dungeon[i][j]>=min){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = min - dungeon[i][j];
                }
            }
        }
        return dp[0][0];
    }
}
/*
地下城数组：
-2  -3  3
-5 -10  1
10  30 -5

dp表：从后往前填写
7  5  2 ∞
6  11 5 ∞
1  1  6 1
∞  ∞  1 0
*/

正难则反：
dp[i][j]表示：进入[i,j]房间并走出终点所需要的最低健康值，可见健康值最低为1，否则进不去[i，j]房间。健康值为0代表勇士死亡，所以勇士走出终点至少要保持健康值为1.

/*
地下城数组：
-2  -3  3
-5 -10  1
10  30 -5

填充后的dp表：从后往前填写
7  5  2 ∞
6  11 5 ∞
1  1  6 1
∞  ∞  1
*/

class Solution {
    public int massage(int[] nums) {
        int n = nums.length;
        if(n==0) return 0;
        if(n==1) return nums[0];
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = nums[0];

        for(int i=2;i<=n;i++){
            int max = dp[i-2];
            for(int j=0;j<i-2;j++){
                max=Math.max(max,dp[j]);
            }
            dp[i] = nums[i-1] + max;
        }
        return dp[n]>dp[n-1]?dp[n]:dp[n-1];
    }
}

dp[i]：代表以nums[i]为结尾的预约序列的最长预约时间。时间复杂度O(N^2)。为了填写当前dp值所需要遍历之前所有写过的dp值。
状态转移方程：dp[i] = nums[i-1] + max;

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

dp[i]：代表从nums[0]到nums[i-1]的最长预约时间。时间复杂度O(N)
状态转移方程：dp[i] = Math.max((nums[i-1] + dp[i-2]),dp[i-1]);
dp[i]代表从nums[0]到nums[i-1]的最长预约时间，所以dp[i]有两种状态：选择了第i个预约或者**没选择第i个预约，**dp[i]要选择两种状态下的最大值。

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

// 大师，我悟了
// 对于多状态的题目就是为每一个状态都创建一个dp表，不过这题的两个dp表可以合成一个，
// 应该没那么好合并，只是这题巧了

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==1) return nums[0];
        // 0、忽略最后一家进行打家劫舍
        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i=2;i<n;i++){
            dp[i] = Math.max((nums[i-1] + dp[i-2]),dp[i-1]);
        }
        // 1、忽略第一家进行打家劫舍
        int[] dp1 = new int[n+1];
        dp1[0] = 0;
        dp1[1] = 0;
        dp1[2] = nums[1];
        for(int i=3;i<=n;i++){
            dp1[i] = Math.max((nums[i-1] + dp1[i-2]),dp1[i-1]);
        }
        // 2、 	返回两个dp表最后一个值的较大值
        return dp[n-1]>dp1[n]?dp[n-1]:dp1[n];
    }
}

核心思路：转化成两个线性的"打家劫舍"（按摩师问题）
核心思路：转化成两个线性的多状态dp问题

这题也是打家劫舍问题：

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = 10001;
        // 1. 预处理
        int[] arr = new int[n];
        for (int x : nums)
            arr[x] += x;
        // 2. dp
        // 创建 dp 表
        // f[i]：选择了第i个数时子问题的最大点数
        // g[i]：没选择第i个数时子问题的最大点数
        int[] f = new int[n];
        int[] g = new int[n];

        // 初始化
        f[0] = arr[0];// f[0]代表选择了nums[0]，所以初始化为arr[0];
        g[0] = 0;// g[0]代表没选择nums[0]，所以初始化为0;
        // 填表
        for (int i = 1; i < n; i++) {
            f[i] = g[i - 1] + arr[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        // 返回值
        return Math.max(f[n - 1], g[n - 1]);
    }
}

题目限制nums[i]的取值范围，所以很轻松的将该问题转化为了打家劫舍问题，不然没那么轻松！！！

• 1 <= nums[i] <= 104

经验：有时候需要将问题进行预处理或者转化才能变成常规的动态规划问题

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

正确性在那里？？？，这题有贪心

多状态：i号房子粉刷的颜色，一共有三种颜色可选，那么就有三个状态表示
创建三个dp表，三张表相互依赖同步填写。

// 第i天处于买入状态有两种可能，此时的收益去两种可能的最大值
dp[0][i]=Math.max(dp[0][i-1],dp[1][i-1]-prices[i]);
// 第i天处于可交易状态有两种可能，此时的收益去两种可能的最大值
dp[1][i]=Math.max(dp[1][i-1],dp[2][i-1]);
// 第i天处于冷冻期状态只有一种可能，及前一天是买入状态并抛售股票
dp[2][i]=dp[0][i-1]+prices[i];

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[3][n];
        dp[0][0] = -prices[0];
        //dp[0][i]:第i天之后处于“买入”状态时的最大利润
        //dp[1][i]:第i天之后处于“可交易”状态时的最大利润
        //dp[2][i]:第i天之后处于“冷冻期”状态时的最大利润

        //三个dp表随着时间推移同时填写
        for(int i=1;i<n;i++){
            dp[0][i]=Math.max(dp[0][i-1],dp[1][i-1]-prices[i]);
            dp[1][i]=Math.max(dp[1][i-1],dp[2][i-1]);
            dp[2][i]=dp[0][i-1]+prices[i];
        }
        // 因为dp[0][n-1]表示最后一天手中有股票没有卖出去，因此不可能是最大收益
        return Math.max(dp[1][n-1],dp[2][n-1]);
    }
}

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[2][n];
        // dp[0][i]:第i天后为持有股票状态
        // dp[1][i]:第i天后为未持有股票
        dp[0][0] = -prices[0];
        for(int i=1;i<n;i++){
            dp[0][i] = Math.max(dp[0][i-1],dp[1][i-1]-prices[i]);
            dp[1][i] = Math.max(dp[1][i-1],dp[0][i-1]+prices[i]-fee);
        }
        // dp[1][n-1]表示最后一天手中持有股票，因此不可能是最大收益
        return dp[1][n-1];
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        // 最多完成两笔交易
        
        // dp[0][i]第i天后的状态为第一次买入
        // dp[1][i]第i天后的状态为第一次卖出
        // dp[2][i]第i天后的状态为第二次买入
        // dp[3][i]第i天后的状态为第二次卖出
        int m = 2;// 允许买卖的次数
        int n = prices.length;
        int[][] dp = new int[2*m][n];
        // 初始化
        dp[0][0] = dp[2][0] = -prices[0];
        for(int i=1;i<n;i++){
            dp[0][i] = Math.max(dp[0][i-1], 0 -prices[i]);
            dp[1][i] = Math.max(dp[1][i-1],dp[0][i-1]+prices[i]);
            dp[2][i] = Math.max(dp[2][i-1],dp[1][i-1]-prices[i]);
            dp[3][i] = Math.max(dp[3][i-1],dp[2][i-1]+prices[i]);
        }
        return Math.max(dp[1][n-1],dp[3][n-1]);
    }
}

该题限制最多进行2次交易，所以会有4种状态，如果最多可以交易m次，就会有2*m个状态，此时在填写dp表的时候可以再加一层for(int j = 0;j<m;j++)完成填表，这样一来这个算法就是通用的买卖股票算法了。

class Solution {
    public int maxProfit(int m, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[2 * m][n];
        // 初始化
        for(int j=0;j<m;j++){
            dp[2*j][0] = -prices[0];    
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int in = 2 * j;
                int out = 2 * j + 1;
                int pre = j == 0 ? 0 : dp[in - 1][i - 1];
                dp[in][i] = Math.max(dp[in][i - 1], pre - prices[i]);
                dp[out][i] = Math.max(dp[out][i - 1], dp[out - 1][i - 1] + prices[i]);
            }
        }
        int max = 0;
        for(int j=0;j<m;j++){
            max = Math.max(dp[2*j+1][n - 1], max);   
        }
        return max;
    }
}

class Solution {
    public int maxProfit(int m, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[2 * m][n];
        // 初始化
        for(int j=0;j<m;j++){
            dp[2*j][0] = -prices[0];    
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int in = 2 * j;
                int out = 2 * j + 1;
                int pre = j == 0 ? 0 : dp[in - 1][i - 1];
                dp[in][i] = Math.max(dp[in][i - 1], pre - prices[i]);
                dp[out][i] = Math.max(dp[out][i - 1], dp[out - 1][i - 1] + prices[i]);
            }
        }
        int max = 0;
        for(int j=0;j<m;j++){
            max = Math.max(dp[2*j+1][n - 1], max);   
        }
        return max;
    }
}

这几个题目就把多状态体现的淋漓尽致了，有了多状态定义dp表的思想，其他的就是编码细节了。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        // 0、正难则反，寻找最小子数组和
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += nums[i];
        int[] dp = new int[n];
        // 1、求最小子数组和（子数组不成环）
        // 通过最小子数组和求得的最大子数组和只包括成环的最大子数组和，
        // 所以要单独再求一次不成环的最大子数组和，然后取两者最大值
        dp[0] = nums[0];
        int min = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(nums[i], dp[i - 1] + nums[i]);
            // dp[i] = dp[i-1]>0?dp[i-1]+nums[i]:nums[i];
            min = Math.min(min, dp[i]);
        }
        // 2、求最大子数组和（子数组不成环）
        int max = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            // dp[i] = dp[i-1]>0?dp[i-1]+nums[i]:nums[i];
            max = Math.max(max, dp[i]);
        }
        // 特殊情况：如果min==sum,说明数组中所有值都小于0
        if(min==sum) return max;
        return Math.max(max,sum-min);
    }
}

正难则反：
做一次最小子数组（非环形）和一次最大子数组和（非环形）

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        // dp[i]：所有以i为结尾的子数组的乘积的最大值
        int[] dpmax = new int[n];
        int[] dpmin = new int[n];
        dpmax[0] = nums[0];
        dpmin[0] = nums[0];
        int max = dpmax[0];
        for (int i = 1; i < n; i++) {
            // 写到这里时发现只定义一个dp表是不够的
            // 还需要顶一个dpmin,dpmin[i]表示所有以i为结尾的子数组的乘积的最小值
            int a = nums[i];
            int b = nums[i]*dpmax[i-1];
            int c = nums[i]*dpmin[i-1];
            dpmax[i] = Math.max(a,Math.max(b,c));
            dpmin[i] = Math.min(a,Math.min(b,c));
            max = Math.max(max,dpmax[i]);
        }
        return max;
        // 测试用例sb
        // return max==1981284352?1000000000:max;
    }
}

需要定义两个dp表。
dpmax[i]：所有以i为结尾的子数组的乘积的最大值
dpmin[i]：所有以i为结尾的子数组的乘积的最小值
在分析状态转移方程的时候发现有最大值有三种情况，其中需要以i-1位置为结尾的乘积最大值和**以i-1位置为结尾的乘积最小值,**此时就可以考虑创建第二个dp表进行辅助做业。
经验：定义dp表的时候可以大胆根据经验进行定义，在分析状态转移方程的时候发现定义的dp表解决不了问题或者一个dp表不够，再根据情况进行调整。

class Solution {
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        // 乘积为正数的子数组
        int[] dp1 = new int[n+1]; 
        // 乘积为负数的子数组，因为乘积为负数的字数也有可能变成正的，所以需创建这个dp表 
        int[] dp2 = new int[n+1]; 
        
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            if(nums[i-1]==0){
                dp1[i] = 0;
                dp2[i] = 0;
            }else if(nums[i-1]>0){
                dp1[i] = dp1[i-1]>0?dp1[i-1]+1:1;
                dp2[i] = dp2[i-1]>0?dp2[i-1]+1:0;
            }else{
                dp1[i] = dp2[i-1]>0?dp2[i-1]+1:0;
                dp2[i] = dp1[i-1]>0?dp1[i-1]+1:1;
            }
            ret = Math.max(ret,dp1[i]);
        }
        return ret;
    }
}
// 真细节啊这题

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        int sum=0;
        for(int i=2;i<n;i++){
            if(2*nums[i-1]==nums[i]+nums[i-2]){
                dp[i] = 1+dp[i-1];
            }
            sum+=dp[i];
        }
        return sum;
    }
}

dp[i]：以i位置为结尾的等差数列的数量

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int[] p = new int[n];
        int[] q = new int[n];
        p[0] = q[0] = 1;
        int max = 1;
        for (int i = 1; i < n; i++) {
            if (i % 2 == 1) {
                if (arr[i - 1] < arr[i]) {
                    p[i] = p[i - 1] + 1;
                    q[i] = 1;
                } else if (arr[i - 1] > arr[i]) {
                    p[i] = 1;
                    q[i] = q[i - 1] + 1;
                } else {
                    p[i] = q[i] = 1;
                }
            } else {
                if (arr[i - 1] > arr[i]) {
                    p[i] = p[i - 1] + 1;
                    q[i] = 1;
                } else if (arr[i - 1] < arr[i]) {
                    p[i] = 1;
                    q[i] = q[i - 1] + 1;
                } else {
                    p[i] = q[i] = 1;
                }
            }
            max = Math.max(max, Math.max(p[i], q[i]));
        }
        return max;
    }
}
// 未进行初始化操作

// 多状态dp表
// p: arr[0]<arr[1]>arr[j]<i
// q: arr[0]>arr[1]<arr[j]>i

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int[] p = new int[n];
        int[] q = new int[n];
        p[0] = q[0] = 1;
        for (int i = 0; i < n; i++) {
            p[i] = q[i] = 1;
        }
        int max = 1;
        for (int i = 1; i < n; i++) {
            if (i % 2 == 1) {
                if (arr[i - 1] < arr[i])
                    p[i] = p[i - 1] + 1;
                if (arr[i - 1] > arr[i])
                    q[i] = q[i - 1] + 1;
            } else {
                if (arr[i - 1] > arr[i])
                    p[i] = p[i - 1] + 1;
                if (arr[i - 1] < arr[i])
                    q[i] = q[i - 1] + 1;
            }
            max = Math.max(max, Math.max(p[i], q[i]));
        }
        return max;
    }
}
// 将所有位置都初始化为了最差情况，填表时就不用考虑这种情况了

// p: arr[0]<arr[1]>arr[j]<i
// q: arr[0]>arr[1]<arr[j]>i

根据题目意思，湍流分为两种，可以创建两个dp表去存储。也就是多状态dp问题
p[i]:以i为结尾的第一种湍流的最长长度。q[i]:以i为结尾的第二种湍流的最长长度。

初始化技巧：

1. 直接初始化dp[0】
2. 加虚拟节点（下标对应）
3. 将所有dp[i]都设置最差的那个情况

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        for(int i=0;i<wordDict.size();i++){
            set.add(wordDict.get(i));
        }
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        // dp[i]:以i位置为结尾是否可以由字典中单词组成
        for(int i=1;i<=n;i++){
            for(int j=i-1;j>=0;j--){
                if(dp[j]&&set.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
}
// 通过示例3可以看出来双指针很难解决这题

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 优化⼀：将字典⾥⾯的单词存在哈希表⾥⾯
        Set<String> hash = new HashSet(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 初始化，保证我们后续填表是正确的
        s = " " + s; // 处理下标的映射关系
        for (int i = 1; i <= n; i++) // 填 dp[i]
        {
            for (int j = i; j >= 1; j--) // 最后⼀个单词的起始位置
            {
                if (dp[j - 1] && hash.contains(s.substring(j, i + 1))) {
                    dp[i] = true;
                    break; // 优化⼆
                }
            }
        }
        return dp[n];
    }
}

小技巧，在字符串开头添加一个空格字符使字符与dp表下标对应
经验：
有时候填写dp[i][j]的时候需要遍历已经已经填冲了的dp表，这个时候需要注意遍历顺序，以及能否提前break，还是需要遍历所有

class Solution {
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        int[] dp = new int[n];
        for(int i=0;i<n;i++) dp[i]=1;
        // dp[i]以i位置结尾的子串的个数
        for(int i=1;i<n;i++){
            int cur = s.charAt(i)-'a';
            int pre = s.charAt(i-1)-'a';
            if((pre + 1)%26 == cur){
                dp[i] = dp[i-1]+1;
            }
        }
        int[] hash = new int[26];
        for(int i=0;i<n;i++){
            int index = s.charAt(i)-'a';
            hash[index] = Math.max(hash[index],dp[i]);
        }
        int sum=0;
        for(int i=0;i<26;i++) sum+=hash[i];
        return sum;
    }
}

// zab
//   i

**难点：**如何去重；
填写dp表，dp[i]代表以i位置为结尾的环绕子字符串的数量。设字符串s=“abcxyzabc”，显然dp[8]代表的所有子字符串包含dp[2]代表的所有子字符串，因此只需要统计以每个字符为结尾的所有dp[i]的最大值，最后将26个值求和即可。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp[i]:以i位置为结尾的最长递增子序列的长度
        int[] dp = new int[n];
        dp[0] = 1;
        int max =dp[0];
        for(int i=1;i<n;i++){
            dp[i] = 1;
            // 1 2 3 4 5
            //         i
            // 需要遍历已经填写了的dp值
            for(int j=i-1;j>=0;j--){
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        // p[i]：以i为结尾的摆动序列，且结尾是递增
        // q[i]：以i为结尾的摆动序列，且结尾是递减
        int[] p = new int[n];
        int[] q = new int[n];
        for(int i=0;i<n;i++) p[i]=q[i]=1;
        int max =1;
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(nums[j]<nums[i]){
                    p[i] =  Math.max(p[i],q[j]+1);
                }else if(nums[j]>nums[i]){
                    q[i] = Math.max(q[i],p[j]+1);
                }else{
                    p[i] =  Math.max(p[i],p[j]);
                    q[i] =  Math.max(q[i],q[j]);
                }
            }
            max = Math.max(max,Math.max(p[i],q[i]));
        }
        return max;
    }
}

多状态

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        // 0、定义dp表
        // 0.0、dp[i]:以i位置为结尾的最长递增子序列的长度
        int[] dp = new int[n];
        // 0.1、count[i]:以i位置为结尾的最长递增子序列的个数
        int[] count = new int[n];
        // 1、初始化
        for (int i = 0; i < n; i++)
            dp[i] = count[i] = 1;

        // 2、定义返回值，将两个表填完之后，遍历两个表就能求出答案
        // 也可以一遍填表，一遍遍历求答案。
        int maxlen = 1;
        int ret = 1;

        for (int i = 1; i < n; i++) {
            // 临时变量好理解一点
            int max = dp[i];// max用于求dp[i]
            int number = count[i];// number用于求count[i]
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    // temp列举了所有以i为结尾的递增子序列的长度
                    int temp = dp[j] + 1;
                    // 求最大长度，以及个数
                    if (temp == max) {
                        number+=count[j];
                    }
                    if (temp > max) {
                        max = temp;
                        number = count[j];
                    }

                }
            }
            dp[i]=max;
            count[i]=number;
            // 求答案
            if(max==maxlen){
                ret+=number;
            }
            if(max>maxlen){
                maxlen=max;
                ret=number;
            }
        }
        
        return ret;
    }
}

小demo:求数组中最大值的出现次数？使用两个变量分别记录最大值和最大值出现的次数。
一开始我只建了一个dp表，发现不行；每一次都是报错调试才发现自己遗漏的点。

class Solution {
    public int findLongestChain(int[][] pairs) {
        // 贪心策略：每次都追加右端点最小的数对
        // 先排序，先以左端点从小到大排序，再以右端点从小到大排序

        // 0、预处理，对数组进行排序
        int n = pairs.length;
        // [1,2][4,5][7,9][7,8][9,10]
        Arrays.sort(pairs, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });
        // 1、定义dp表
        int[] dp = new int[n];
        for(int i=0;i<n;i++) dp[i]=1;
        int ret = 1;
        // 2、填表
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(pairs[i][0]>pairs[j][1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}
// 排序前：
// pairs:[[-6,9],[1,6],[8,10],[-1,4],[-6,-2],[-9,8],[-5,3],[0,3]]
// pairs:[[-9,8],[-6,-2],[-6,9],[-5,3],[-1,4],[0,3],[1,6],[8,10]]

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> hash = new HashMap<>();
        int n = arr.length;
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int temp = hash.getOrDefault(arr[i] - difference, 0) + 1;
            hash.put(arr[i], temp);
            ret = Math.max(ret, temp);
            //ret = Math.max(ret, arr[i);
        }
        return ret;
    }
}
// arr = [1,5,7,8,5,3,4,2,1], difference = -2
// 12345345

在哈希表中做动态规划
hash.get()的时间复杂度为O(logN)。如用变量temp存储hash.get()的返回值，避免多次使用hash.get()，节约时间。

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        // 只有固定前两个数，斐波那契数列才算
        // 复合斐波那数列特点的子序列
        // 数组是严格递增的
        int n = arr.length;
        Set<Integer> hash = new HashSet<>();
        for(int x:arr) hash.add(x);
        int ret = 2;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[i];
                int b = arr[j];
                int len = 2;
                while (hash.contains(a + b)) {
                    int temp = a + b;
                    a = b;
                    b = temp;
                    len++;
                }
                ret = Math.max(ret, len);
            }
        }
        return ret==2?0:ret;
    }
}
// 这明显不是动态规划的思路，利用的数组递增的性质

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        // 优化：将 数组中的元素 + 下标 绑定在⼀起，扔到哈希表中
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        int n = arr.length;
        for (int i = 0; i < n; i++)
            hash.put(arr[i], i);
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dp[i][j] = 2;

        int ret = 2;
        for (int j = 2; j < n; j++) // 固定最后⼀个数
            for (int i = 1; i < j; i++) // 枚举倒数第⼆个数
            {
                int a = arr[j] - arr[i];
                if (a < arr[i] && hash.containsKey(a))
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                ret = Math.max(ret, dp[i][j]);
            }
        return ret < 3 ? 0 : ret;

    }
}
// 动态规划解法

因为等差序列的确定至少需要两个元素，所以dp表说二维的

class Solution {
    public int longestArithSeqLength(int[] nums) {
        // 优化
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(nums[0], 0);
        // 建表
        int n = nums.length;

        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) // 初始化
            Arrays.fill(dp[i], 2);

        int ret = 2;
        for (int i = 1; i < n; i++) // 固定倒数第⼆个数
        {
            for (int j = i + 1; j < n; j++) // 枚举倒数第⼀个数
            {
                int a = 2 * nums[i] - nums[j];
                if (hash.containsKey(a)) {
                    // 填表的核心逻辑	
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            hash.put(nums[i], i);
        }
        return ret;
    }
}

对于等差数列，一个数是确定不了数列的通式的，所以dp表要定义为二维的

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        Map<Long, List<Integer>> hash = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        list.add(0);
        hash.put((long)nums[0], list);
        int n = nums.length;
        int[][] dp = new int[n][n];
        int sum = 0;
        for (int i = 1; i < n; i++) // 固定倒数第⼆个数
        {
            for (int j = i + 1; j < n; j++) // 枚举倒数第⼀个数
            {
                long a = 2L*nums[i] - nums[j];
                if (hash.containsKey(a)) {
                    for (int k : hash.get(a)) {
                        dp[i][j] += dp[k][i] + 1;
                    }
                }
                sum += dp[i][j];
            }
            if (hash.containsKey((long)nums[i])) {
                hash.get((long)nums[i]).add(i);
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(i);
                hash.put((long)nums[i], temp);
            }
        }
        return sum;
    }
}

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        // 优化
        Map<Long, List<Integer>> hash = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            long tmp = (long) nums[i];
            if (!hash.containsKey(tmp))
                hash.put(tmp, new ArrayList<Integer>());
            hash.get(tmp).add(i);
        }
        int[][] dp = new int[n][n];
        int sum = 0;
        for (int j = 2; j < n; j++) // 固定倒数第⼀个数
            for (int i = 1; i < j; i++) // 枚举倒数第⼆个数
            {
                long a = 2L * nums[i] - nums[j];
                if (hash.containsKey(a)) {
                    for (int k : hash.get(a))
                        if (k < i)
                            dp[i][j] += dp[k][i] + 1;
                        else
                            break; // ⼩优化
                }
                sum += dp[i][j];
            }
        return sum;
    }
}

class Solution {
    public int countSubstrings(String s) {
        // 1、中心扩展算法
        char[] str = s.toCharArray();
        int n = str.length;
        int sum=0;
        for(int i=0;i<n;i++){
            // 2、长度为偶数的回文子串
            int left = i;
            int right = i+1;
            while(0<=left && right<n && str[left]==str[right]){
                left--;
                right++;
            }
            sum+=i-left;
            // 3、长度为奇数的回文子串
            left = i-1;
            right = i+1;
            while(0<=left && right<n && str[left]==str[right]){
                left--;
                right++;
            }
            sum+=i-left;
        }
        return sum;
    }
}

// 马拉车算法解决回文串

//动态规划算法解决回文串
class Solution {
    public int countSubstrings(String s) {
        // 确定状态表示

        // dp[i]:以i位置为中心的回文子串个数，如果是这样定义那么就是刚才的中心扩展算法来，并且没有状态转移方程

        // 二维状态表
        int n = s.length();
        // 子串s.substring(i,j+1)是否是回文字符串
        boolean[][] dp = new boolean[n+1][n+1];
        int sum = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j-i<=1)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
                if(dp[i][j]) sum++;
            }
        }
        return sum;
    }
}

之前是使用布尔数组存储子串是否会回文，改用int存储回文串的长度即可。

class Solution {
    public String longestPalindrome(String ss) {
        // 马拉车算法
        // 动态规划
        int n = ss.length();
        int[][] dp = new int[n][n];
        
        int max = 1;// 回文子串的最大值
        int left = n-1;// 最大回文子串的左端点
        int right = n-1;// 最大回文子串的右端点
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (ss.charAt(i) == ss.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = j - i + 1;
                    } else if (dp[i + 1][j - 1] > 0) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                }
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    left = i;
                    right = j;
                }
            }
        }
        return ss.substring(left, right + 1);
    }
}

先计算出所有回文子串，再使用双指针判断原字符串能否有三个回文子串拼接而成

class Solution {
    public boolean checkPartitioning(String s) {
        // 0、先填表
        // 1、双指针遍历

        int n = s.length();
        // 子串s.substring(i.j+1)是否是回文字符串
        boolean[][] dp = new boolean[n+1][n+1];
        // 0、填表
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j-i<=1)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }

        // 1、双指针遍历
        for(int i=1;i<n-1;i++){
            for(int j=i;j<n-1;j++){
                if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true;
            }
        }
        return false;
    }
}

class Solution {
    public int minCut(String s) {
        // 分割字符串为若干回文子串，问最少需要几次分割

        // 0、先填表
        // 1、然后再做一次动态规划

        int n = s.length();
        // 子串s.substring(i.j+1)是否是回文字符串
        boolean[][] dp = new boolean[n+1][n+1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j-i<=1)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }
        int[] count = new int[n];
        for(int i=0;i<n;i++){
            count[i] = i; // 这一步初始化很重要，将count[i]初始为最大值，然后有更小的情况再更新
            for(int j=i;j>=0;j--){
                if(dp[j][i]){
                    if(j==0){
                        count[i] = 0;// 已是回文串无需插入字符
                        break;
                    } 
                    count[i] = Math.min(count[i],count[j-1]+1);
                }
            }            
        }
        return count[n-1];
    }
}

两次动态规划

class Solution {
    public int longestPalindromeSubseq(String ss) {
        // 一维的状态表是不可能的了

        int n = ss.length();
        int[][] dp = new int[n][n];
        
        int max = 1;// 回文子串的最大值
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (ss.charAt(i) == ss.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = j - i + 1;
                    } else if (dp[i + 1][j - 1] > 0) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                }else{
                    // 这个状态转移很重要
                    dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
                }
                max = Math.max(max,dp[i][j]);
            }
        }
        return max;
    }
}
// 动态规划：
// 0、状态表示
// 1、状态转移方程
// 2、填表顺序
// 3、初始化