算法篇：动态规划I

  • 开发
  • 29

声明：若未特殊标出，则默认是leedcode原题。

1、1137.第N个泰波那契数列：
①状态表示：dp[i]表示：第i个泰波那契数的值。
②状态转移方程：以i位置的状态，最近的一步，来划分问题：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
③初始化：dp[0] = 0  dp[1] = dp[2] = 1
④填表顺序：从左往右。
⑤返回值：dp[n]

class Solution 
{
public:
    int tribonacci(int n) 
    {
        // 0、处理边界情况
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        // 1、创建dp表
        vector<int> dp(n+1);

        // 2、初始化
        dp[0] = 0, dp[1] = dp[2] = 1;

        // 3、填表
        for(int i = 3; i <= n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        // 4、返回值
        return dp[n];
    }
};

利用滚动数组优化：

class Solution 
{
public:
    int tribonacci(int n) 
    {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        int a = 0, b = 1, c = 1, d;

        for(int i = 3; i <= n; i++)
        {
            d = a + b + c;
            // 滚动操作
            a = b; b = c; c = d;
        }

        return d;
    }
};

2、面试题 08.01.三步问题
①状态表示：dp[i]表示到达i位置时，一共有多少种方法。
②状态转移方程：以i位置的状态，最近的一步，来划分问题：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
③初始化：dp[1] = 1  dp[2] = 2  dp[3] = 4
④填表顺序：从左往右。
⑤返回值：dp[n]

class Solution 
{
public:
    int waysToStep(int n) 
    {
        // 0、处理边界情况
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;

        const int MOD = 1e9 + 7;

        // 1、创建dp表
        vector<int> dp(n+1);

        // 2、初始化
        dp[0] = 0, dp[1] = 1, dp[2] = 2, dp[3] = 4;

        // 3、填表
        for(int i = 4; i <= n; i++)
        {
            dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
        }

        // 4、返回值
        return dp[n];
    }
}

3、746.使用最小花费爬楼梯

解法一：
①状态表示：dp[i]表示到达i位置时，最小花费。
②状态转移方程：用之前/之后的状态，推导出dp[i]的值。根据最近的一步，来划分问题：
先到达i-1位置，然后支付cost[i-1]，走一步：dp[i] = dp[i-1] + cost[i-1]
先到达i-2位置，然后支付cost[i-2]，走两步：dp[i] = dp[i-2] + cost[i-2]
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
③初始化：保证填表时不越界：dp[0] = dp[1] = 0
④填表顺序：从左往右。
⑤返回值：dp[n]

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        // 1、创建dp表
        int n = cost.size();
        vector<int> dp(n+1);

        // 2、初始化(vector默认初始值为0)
        // dp[0] = dp[1] = 0;

        // 3、填表
        for(int i = 2; i <= n; i++)
        {
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }

        // 4、返回值
        return dp[n];
    }
};

解法二：
①状态表示：从i位置出发，到达楼顶，此时的最小花费。
②状态转移方程：用之前/之后的状态，推导出dp[i]的值。根据最近的一步，来划分问题：
支付cost[i]，走一步，到达i+1位置出发到终点：dp[i] = dp[i+1] + cost[i]
支付cost[i]，走两步，到达i+2位置出发到终点：dp[i] = dp[i+2] + cost[i]
dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i]);
③初始化：保证填表时不越界：dp[n-1] = cost[n-1]  dp[n-2] = cost[n-2]
④填表顺序：从右往左。
⑤返回值：min(dp[0]，dp[1])

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        // 1、创建dp表
        int n = cost.size();
        vector<int> dp(n);

        // 2、初始化
        dp[n-1] = cost[n-1], dp[n-2] = cost[n-2];

        // 3、填表
        for(int i = n - 3; i >= 0; i--)
            dp[i] =  cost[i] + min(dp[i+1], dp[i+2]);

        // 4、返回值
        return min(dp[0], dp[1]);
    }
};

4、91.解码方法
①状态表示：dp[i]表示到达i位置时，解码方法的总数。
②状态转移方程：根据最近的一步，来划分问题：
s[i]单独解码：    成功（1<=a<=9)：dp[i-1]                    失败：0
s[i-1]与s[i]解码：成功（10<=b*10+a<=26)：dp[i-2]      失败：0
dp[i] = dp[i-1] + dp[i-2]
③初始化：dp[0] =0/1     dp[1] = 0/1/2
④填表顺序：从左往右。
⑤返回值：dp[n-1]

class Solution 
{
public:
    int numDecodings(string s) 
    {
        // 1、创建dp表
        int n = s.size();
        vector<int> dp(n);

        // 2、初始化
        dp[0] = s[0] != '0';

        if(n == 1 || dp[0] == 0) return dp[0]; // 处理边界情况

        if(s[0] != 0 && s[1] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + s[1] - '0';
        if(t >= 10 && t <= 26) dp[1] += 1;
 
        // 3、填表
        for(int i = 2; i < n; i++)
        {
            if(s[i] != '0') dp[i] += dp[i-1];
            int q = (s[i-1] - '0') * 10 + s[i] - '0';
            if(q >= 10 && q <= 26)  dp[i] += dp[i-2];
        }
        // 4、返回值
        return dp[n-1];
    }
};

优化原理：处理边界问题以及初始化问题的技巧（虚拟节点）
注意事项：
①虚拟节点里面的值，要保证后面的填表是正确的。
②下标的映射关系。

class Solution 
{
public:
    int numDecodings(string s) 
    {
        // 优化
        // 1、创建dp表
        int n = s.size();
        vector<int> dp(n + 1);

        // 2、初始化
        dp[0] = 1;
        dp[1] = s[1 - 1] != '0';

        // 3、填表
        for(int i = 2; i <= n; i++)
        {
            if(s[i - 1] != '0') dp[i] += dp[i - 1];
            int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if(t >= 10 && t <= 26)  dp[i] += dp[i - 2];
        }
        // 4、返回值
        return dp[n];
    }
};

5、62.不同路径
①状态表示：dp[i][j]表示到达[i,j]位置时，一共有多少种方式。
②状态转移方程：根据最近的一步，来划分问题：
从[i-1,j]→[i,j]→dp[i-1][j]
从[i,j-1]→[i,j]→dp[i][j-1]
dp[i][j] = dp[i-1][j] + dp[i][j-1]
③初始化：增添一行和一列的虚拟节点。
④填表顺序：从上往下填写每一行，每一行从左往右。
⑤返回值：dp[m][n]

class Solution 
{
public:
    int uniquePaths(int m, int n) 
    {
        // 1、创建dp表
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        // 2、初始化
        dp[0][1] = 1;

        // 3、填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        // 4、返回值
        return dp[m][n];
    }
};

6、63.不同路径II(有障碍物）

class Solution 
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) 
    {
        // 1、创建dp表
        int m = ob.size(), n = ob[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        // 2、初始化
        dp[0][1] = 1;

        // 3、填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(ob[i - 1][j - 1] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        // 4、返回值
        return dp[m][n];
    }
};

8、931.下降路径最小和
①状态表示：dp[i][j]表示到达[i,j]位置时，最小的下降路径。
②状态转移方程：根据最近的一步，来划分问题：
从[i-1,j-1]→[i,j]→x=dp[i-1][j-1]+m[i][j]
从[i-1, j ]→[i,j]→y=dp[i-1][ j ]+m[i][j]
从[i-1,j+1]→[i,j]→z=dp[i-1][j+1]+m[i][j]
dp[i][j] = min(x,y,z)+m[i][j]
③初始化：增添一行和两列虚拟节点，所有位置填正无穷，第一行改为0。
④填表顺序：从上往下填写每一行。
⑤返回值：最后一行最小值。

class Solution 
{
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        int n = matrix.size();
        // 1、创建dp表
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));

        // 2、初始化第一行
        for(int j = 0; j <= n + 1; j++) dp[0][j] = 0;

        // 3、填表
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i - 1][j - 1];
        
        int ret = INT_MAX;

        // 4、返回值
        for(int j = 1; j <= n; j++)
            ret = min(ret, dp[n][j]);
        return ret;
    }
};

10、174.地下城游戏（有后效性）
①状态表示：
错误状态表示：dp[i][j]表示从起点出发，到达[i,j]位置时，所需最低初始健康点数。（以某位置为结尾）
正确状态表示：dp[i][j]表示从[i,j]位置出发，到达终点时，所需最低初始健康点数。（以某位置为起点）
②状态转移方程：根据最近的一步，来划分问题：
向右走：dp[i][j]=dp[i][j+1]-d[i][j]
向下走：dp[i][j]=dp[i+1][j]-d[i][j]
dp[i][j] = min(dp[i][j+1]，dp[i+1][j])-d[i][j]，由于最低健康点数为1，故dp[i][j]=max(1,dp[i][j])。
③初始化：最右和最下面分别增添一列/行虚拟节点，保证最低健康血量为1，其余填正无穷大即可。
④填表顺序：从下往上填写每一行，每一行从右往左。
⑤返回值：dp[0][0]

class Solution 
{
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        int m = dungeon.size(), n = dungeon[0].size();

        // 1、创建dp表
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        // 2、初始化
        dp[m-1][n] = dp[m][n-1] = 1;

        // 3、填表
        for(int i = m - 1; i >= 0; i--)
            for(int j = n - 1; j >=0; j--)
                dp[i][j] = max(1, min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]);

        // 4、返回值
        return dp[0][0];
    }
};

11、打家劫舍I：按摩师
①状态表示：选择到i位置的时候，此时的最长预约时长。
f[i]表示：选择到i位置的时候，nums[i]必选，此时的最长预约时长。
g[i]表示：选择到i位置的时候，nums[i]不选，此时的最长预约时长。
②状态转移方程：
i处选：    f[i]=g[i-1]+nums[i]
i处不选：i-1处选：    g[i]=f[i-1]
               i-1处不选：g[i]=g[i-1]
               g[i]=max(f[i-1],g[i-1])
③初始化：此处没有必要加虚拟节点，f[0]=nums[0]，g[0]=0。
④填表顺序：从左往右，两个表一起填。
⑤返回值：max(f[n-1],g[n-1])

class Solution 
{
public:
    int massage(vector<int>& nums) 
    {
        // 0、处理边界条件
        int n = nums.size();
        if(n == 0) return 0;

        // 1、创建dp表
        vector<int> f(n), g(n);

        // 2、初始化
        f[0] = nums[0];

        // 3、填表
        for(int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1],g[i - 1]);
        }
        
        // 4、返回值
        return max(f[n - 1],g[n - 1]);
    }
};

12、213.打家劫舍II
①状态表示：通过分类讨论，将环形的问题，转化成两个线性的“打家劫舍I”。
f[i]表示：偷到i位置时，偷nums[i]，此时的最大金额。
g[i]表示：偷到i位置时，不偷nums[i]，此时的最大金额。
②状态转移方程：
i处偷：    f[i]=g[i-1]+nums[i]
i处不偷：i-1处偷：    g[i]=f[i-1]
               i-1处不偷：g[i]=g[i-1]
               g[i]=max(f[i-1],g[i-1])
③初始化：此处没有必要加虚拟节点，f[0]=nums[0]，g[0]=0。
④填表顺序：从左往右，两个表一起填。
⑤返回值：max(f[n-1],g[n-1])

class Solution 
{
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }

    int rob1(vector<int>& nums, int left, int right) 
    {
        // 0、处理边界条件
        if(left > right) return 0;
        int n = nums.size();

        // 1、创建dp表
        vector<int> f(n), g(n);

        // 2、初始化
        f[left] = nums[left];

        // 3、填表
        for(int i = left + 1; i <= right; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1],g[i - 1]);
        }
        
        // 4、返回值
        return max(f[right], g[right]);
    }
};

13、740.删除并获得点数
①状态表示：预处理：将数组中的数，统计到arr中，做一次“打家劫舍I”问题即可。
②状态转移方程：
i处选：    f[i]=g[i-1]+arr[i]
i处不选：i-1处选：    g[i]=f[i-1]
               i-1处不选：g[i]=g[i-1]
               g[i]=max(f[i-1],g[i-1])
③初始化：此处没有必要加虚拟节点，f[0]=arr[0]，g[0]=0。
④填表顺序：从左往右，两个表一起填。
⑤返回值：max(f[n-1],g[n-1])

class Solution 
{
public:
    int deleteAndEarn(vector<int>& nums) 
    {
        const int N = 10001;
        // 0、预处理
        vector<int> arr(N);
        for(auto x : nums) arr[x] += x;

        // 1、创建dp表
        vector<int> f(N), g(N);

        // 2、初始化
        f[0] = arr[0];

        // 3、填表
        for(int i = 1; i < N; i++)
        {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(f[i - 1],g[i - 1]);
        }
        
        // 4、返回值
        return max(f[N - 1],g[N - 1]);
    }
};

14、LCR 091.粉刷房子
①状态表示：
dp[i][0]表示：粉刷到i位置时，粉刷上红色，此时的最小花费。
dp[i][1]表示：粉刷到i位置时，粉刷上蓝色，此时的最小花费。
dp[i][2]表示：粉刷到i位置时，粉刷上绿色，此时的最小花费。
②状态转移方程：
dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i][0]
dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i][1]
dp[i][2]=min(dp[i-1][0],dp[i-1][1])+costs[i][2]
③初始化：加一列虚拟节点并初始化为0。
④填表顺序：从左往右，三个表一起填。
⑤返回值：min(dp[n][0],dp[n][1],dp[n][2])

class Solution 
{
public:
    int minCost(vector<vector<int>>& costs) 
    {
        // 1、创建dp表
        int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int>(3));

        // 2、初始化

        // 3、填表
        for(int i = 1; i <= n; i++)
        {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        
        // 4、返回值
        return min(dp[n][0], min(dp[n][1], dp[n][2]));
    }
};

15、309.买卖股票的最佳时期I（含冷冻期）
①状态表示：
dp[i][0]表示：第i天结束后，处于“买入”状态，此时的最大利润。
dp[i][1]表示：第i天结束后，处于“可交易”状态，此时的最大利润。
dp[i][2]表示：第i天结束后，处于“冷冻期”状态，此时的最大利润。
②状态转移方程：（状态机）
dp[i][0]=max(dp[i-1][0],dp[i-1][0]-prices[i-1])
dp[i][1]=max(dp[i-1][1],dp[i-1][2])
dp[i][2]=dp[i-1][0]+prices[i]
③初始化：dp[0][0]=-p[0]   dp[0][1]=0   dp[0][2]=0
④填表顺序：从左往右，三个表一起填。
⑤返回值：max(dp[n-1][1],dp[n-1][2])

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        // 1、创建dp表
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));

        // 2、初始化
        dp[0][0]=-prices[0];

        // 3、填表
        for(int i = 1; i < n; i++)
        {
            dp[i][0]=max(dp[i - 1][0], dp[i - 1][1]-prices[i]);
            dp[i][1]=max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2]=dp[i - 1][0] + prices[i];
        }
        
        // 4、返回值
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

16、714.买卖股票的最佳时期II（含手续费）
①状态表示：
f[i]表示：第i天结束后，处于“买入”状态，此时的最大利润。
g[i]表示：第i天结束后，处于“卖出”状态，此时的最大利润。
②状态转移方程：（状态机）
f[i]=max(f[i-1],g[i-1]-prices[i])
g[i]=max(g[i-1],f[i-1]+prices[i]-fee)
③初始化：f[0]=-prices[0]   g[0]=0
④填表顺序：从左往右，两个表一起填。
⑤返回值：g[n-1]

class Solution 
{
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        // 1、创建dp表
        int n = prices.size();
        vector<int> f(n), g(n);

        // 2、初始化
        f[0]=-prices[0];

        // 3、填表
        for(int i = 1; i < n; i++)
        {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
        
        // 4、返回值
        return g[n - 1];
    }
};

17、714.买卖股票的最佳时期III
①状态表示：
f[i][j]表示：第i天结束后，完成了j次交易，此时处于“买入”状态，此时的最大利润。
g[i][j]表示：第i天结束后，完成了j次交易，处于“卖出”状态，此时的最大利润。
②状态转移方程：（状态机）
f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i])
g[i]=g[i-1][j]   if(j-1>=0) g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i])
③初始化：f[0][0]=-prices[0]  g[0][0]=0   f[0][1]=f[0][2]=g[0][1]=g[0][2]=-0x3f3f3f3f
④填表顺序：从上往下填写每一行，每一行从左往右，两个表一起填。
⑤返回值：g表的最后一行里面的最大值。

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int maxProfit(vector<int>& prices) 
    {
        // 1、创建dp表
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INF));
        auto g = f;

        // 2、初始化
        f[0][0] = -prices[0], g[0][0] = 0;

        // 3、填表
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        
        // 4、返回值
        int ret = 0;
        for(int j = 0; j < 3; j++)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};

19、53.最大子数组和
①状态表示：dp[i]以i位置元素为结尾的所有子数组的最大和。
②状态转移方程：
长度为一：dp[i]=nums[i]
长度大于一：dp[i]=dp[i-1]+nums[i]
dp[i]=max(nums[i],dp[i-1]+nums[i])
③初始化：虚拟节点：dp[0]=0
④填表顺序：从左往右。
⑤返回值：整个dp表里的最大值

class Solution 
{
public:
    int maxSubArray(vector<int>& nums) 
    {
        // 0、处理边界条件
        int n = nums.size();
        if(n == 0) return 0;

        // 1、创建dp表
        vector<int> dp(n + 1);

        int ret = INT_MIN;  4、返回值
        // 2、初始化

        // 3、填表
        for(int i = 1; i <= n; i++)
        {
            dp[i] = max(nums[i - 1], dp[i - 1] + nums[i-1]);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

20、53.最大子数组和
①状态表示：
f[i]表示：以i位置元素为结尾的所有子数组的最大和。
g[i]表示：以i位置元素为结尾的所有子数组的最小和。
②状态转移方程：
长度为一：f[i]=nums[i]
长度大于一：f[i]=dp[i-1]+nums[i]
f[i]=max(nums[i],f[i-1]+nums[i])
长度为一：g[i]=nums[i]
长度大于一：g[i]=g[i-1]+nums[i]
g[i]=min(nums[i],g[i-1]+nums[i])
③初始化：虚拟节点：dp[0]=0
④填表顺序：从左往右，两个表一起填。
⑤返回值：sum==gmin?fmax:max(fmax,sum-gmin)

class Solution 
{
public:
    int maxSubarraySumCircular(vector<int>& nums) 
    {
        // 1、创建dp表
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);

        int fmax = INT_MIN, gmin = INT_MAX, sum = 0; 

        // 2、初始化

        // 3、填表
        for(int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];
            f[i] = max(x, f[i - 1] + x);
            fmax = max(fmax, f[i]);
            g[i] = min(x, g[i - 1] + x);
            gmin = min(gmin, g[i]);
            sum += x;
        }
        // 4、返回值
        return sum == gmin ? fmax : max(fmax, sum - gmin);
    }
};

21、152.乘积最大子数组
①状态表示：
f[i]表示：以i位置元素为结尾的所有子数组的最大积。
g[i]表示：以i位置元素为结尾的所有子数组的最小积。
②状态转移方程：
长度为一：f[i]=nums[i]
长度大于一：if(nums[i]>0) f[i]=f[i-1]*nums[i]
                      if(nums[i]<0) f[i]=g[i-1]*nums[i]
f[i]=max(nums[i],f[i-1]*nums[i],g[i-1]*nums[i])
长度为一：f[i]=nums[i]
长度大于一：if(nums[i]>0) g[i]=g[i-1]*nums[i]
                      if(nums[i]<0) g[i]=f[i-1]*nums[i]
g[i]=min(nums[i],g[i-1]*nums[i],f[i-1]*nums[i])
③初始化：虚拟节点：f[0]=g[0]=1
④填表顺序：从左往右，两个表一起填。
⑤返回值：f表中的最大值。

class Solution 
{
public:
    int maxProduct(vector<int>& nums) 
    {
        // 1、创建dp表
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);

        int ret = INT_MIN; 

        // 2、初始化
        f[0] = g[0] = 1;

        // 3、填表
        for(int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];
            f[i] = max(x, max(f[i - 1] * x, g[i - 1] * x));
            g[i] = min(x, min(g[i - 1] * x, f[i - 1] * x));
            ret = max(ret, f[i]);
        }
        // 4、返回值
        return ret;
    }
};

22、1567. 乘积为正数的最长子数组长度
①状态表示：
f[i]表示：以i位置元素为结尾的所有子数组中乘积为正数的最长长度  。
g[i]表示：以i位置元素为结尾的所有子数组中乘积为负数的最长长度 。
②状态转移方程：
长度为一：   if(nums[i]>0) f[i]=1
                     if(nums[i]<0) f[i]=0
长度大于一：if(nums[i]>0) f[i]=f[i-1]+1
                      if(nums[i]<0) f[i]=g[i-1]==0?0:g[i-1]+1
故if(nums[i]>0) f[i]=f[i-1]+1
    if(nums[i]<0) f[i]=g[i-1]==0?0:g[i-1]+1

长度为一：   if(nums[i]>0) g[i]=0
                     if(nums[i]<0) g[i]=1
长度大于一：if(nums[i]>0) g[i]=g[i-1]==0?0:g[i-1]+1
                      if(nums[i]<0) g[i]=f[i-1]+1
故if(nums[i]>0) g[i]=g[i-1]==0?0:g[i-1]+1
    if(nums[i]<0) g[i]=f[i-1]+1
③初始化：虚拟节点：f[0]=g[0]=0
④填表顺序：从左往右，两个表一起填。
⑤返回值：f表中的最大值。 

class Solution 
{
public:
    int getMaxLen(vector<int>& nums) 
    {
        // 1、创建dp表
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);

        int ret = INT_MIN; 

        // 2、初始化

        // 3、填表
        for(int i = 1; i <= n; i++)
        {
            if(nums[i - 1] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            } 
            else if(nums[i - 1]<0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(ret, f[i]);
        }
        // 4、返回值
        return ret; 
    }
};

23、413.等差数列划分
①状态表示：
dp[i]表示：以i位置元素为结尾的所有子数组中有多少个等差数列。
②状态转移方程：
if(c-b==b-a) dp[i]=dp[i-1]+1
if(c-b!=b-a) dp[i]=0
dp[i]=c-b==b-a?dp[i-1]+1:0
③初始化：dp[0]=dp[1]=0
④填表顺序：从左往右。
⑤返回值：dp表内所有元素的和。

class Solution 
{
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        // 1、创建dp表
        int n = nums.size();
        vector<int> dp(n);

        int ret = 0;
        // 2、初始化

        // 3、填表
        for(int i = 2; i < n; i++)
        {
            dp[i] = nums[i] - nums[i-1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            ret += dp[i];
        }

        // 4、返回值
        return ret; 
    }
};

24、413.最长湍流子数组
①状态表示：
错误状态表示：以i位置元素为结尾的所有子数组中，最长湍流子数组的长度。
正确状态表示：
f[i]表示:以i位置元素为结尾的所有子数组中，最后呈现“上升”状态的最长湍流子数组的长度。
g[i]表示:以i位置元素为结尾的所有子数组中，最后呈现“下降”状态的最长湍流子数组的长度。
②状态转移方程：
if(a>=b) f[i]=1
if(a<b) f[i]=g[i-1]+1√
f[i]=a>=b?1:g[i-1]+1
if(a>b) g[i]=f[i-1]+1√
if(a<=b) g[i]=1
g[i]=a>b?g[i-1]+1:1
③初始化：f表和g表初始化为1
④填表顺序：从左往右，两个表一起填。
⑤返回值：f表与g表内最大值。

class Solution 
{
public:
    int maxTurbulenceSize(vector<int>& nums) 
    {
        // 1、创建dp表 // 2、初始化
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1);

        int ret = 1;
        

        // 3、填表
        for(int i = 1; i < n; i++)
        {
            if(nums[i - 1] < nums[i]) f[i] = g[i - 1] + 1;
            else if(nums[i - 1] > nums[i]) g[i] = f[i - 1] + 1;
            ret = max(ret, max(f[i], g[i]));
        }

        // 4、返回值
        return ret; 
    }
};

25、139. 单词拆分
①状态表示：
dp[i]表示:[0,i]区间内的字符串，能否被字典中的单词拼接而成。
②状态转移方程：根据最后一个位置的情况，来划分问题。设j为最后一个单词起始位置的下标（0<=j<=i）。
if(dp[j-1]==true&&s[j~i]在字典中，dp[i]=true
else dp[i]=false
③初始化：虚拟节点确保后续填表正确dp[0]=true，下标的映射关系s='_'+s
④填表顺序：从左往右。
⑤返回值：dp[n]。

class Solution 
{
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        unordered_set<string> hash;
        for(auto& s : wordDict) hash.insert(s);

        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true; // 保证后续填表是正确的
        s = ' ' + s; // 使原始字符串的下标统一+1
        for(int i = 1; i <= n; i++) // 填dp[i]
        {
            for(int j = i; j >= 1; j--) // 最后一个单词的起始位置
            {
                if(dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

26、467. 环绕字符串中唯一的子字符串
①状态表示：
dp[i]表示:以i位置的元素为结尾的所有子串里面，有多少个在base中出现过。
②状态转移方程：
长度为一：dp[i]=1
长度大于一：if(s[i-1]+1==s[i]||s[i-1]=='z'&&s[i]=='a') dp[i]=dp[i-1]
dp[i]=1+dp[i-1]
③初始化：dp表里的值都初始化为1。
④填表顺序：从左往右。
⑤返回值：返回dp表中所有元素的和。

去重：相同字符结尾的dp值，取最大的即可
1、创建一个大小为26的数组。
2、里面的值保存相应字符结尾的最大的dp值即可。
3、返回数组里的和。

class Solution 
{
public:
    int findSubstringInWraproundString(string s) 
    {
        int n = s.size();
        vector<int> dp(n, 1);
        for(int i = 1; i < n; i++)
        {
            if(s[i - 1]+1 == s[i] || s[i - 1] == 'z' && s[i] == 'a')
            dp[i] += dp[i - 1];
        }

        int hash[26] = { 0 };
        for(int i = 0; i < n; i++)
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);

        int sum = 0;
        for(auto& x : hash) sum += x;
        return sum;
    }
};

27、300.最长递增子序列
①状态表示：
dp[i]表示:以i位置的元素为结尾的所有子序列里面，最长递增子序列的长度。
②状态转移方程：
长度为一：dp[i]=1
长度大于一：if（nums[j]<nums[i]) dp[i]=max(dp[j]+1)
③初始化：dp表里的值都初始化为1。
④填表顺序：从左往右。
⑤返回值：返回dp表中的最大值。

class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
                if(nums[j] < nums[i]) 
                    dp[i] = max(dp[i], dp[j] + 1);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

28、376. 摆动序列
①状态表示：
dp[i]表示:以i位置的元素为结尾的所有子序列里面，最长摆动序列的长度。×
f[i]表示:以i位置的元素为结尾的所有子序列里面，最后一个位置呈现“上升”趋势的最长摆动序列的长度。
g[i]表示:以i位置的元素为结尾的所有子序列里面，最后一个位置呈现“下降”趋势的最长摆动序列的长度。
②状态转移方程：
（上升）长度为一：f[i]=1
长度大于一：if（nums[j]<nums[i]) f[i]=max(g[j]+1)
（下降）长度为一：g[i]=1
长度大于一：if（nums[j]>nums[i]) g[i]=max(f[j]+1)
③初始化：dp表里的值都初始化为1。
④填表顺序：从左往右。
⑤返回值：f表和g表中的最大值。

class Solution 
{
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1);
        int ret = 1;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i]) f[i] = max(f[i], g[j] + 1);
                else if(nums[j] > nums[i]) g[i] = max(g[i], f[j] + 1);
            }
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};

29、673. 最长递增子序列的个数
①状态表示：
dp[i]表示:以i位置的元素为结尾的所有子序列里面，最长递增子序列的个数。×
len[i]表示:以i位置的元素为结尾的所有子序列里面，最长递增子序列的长度。
count[i]表示:以i位置的元素为结尾的所有子序列里面，最长递增子序列的个数。
②状态转移方程：
if(len[j]+1==len[i]) count[i]+=count[j]
if(len[j]+1<len[i]) 无视
if(len[j]+1>len[i]) len[i]=len[j]+1; count[i]=count[j]
③初始化：len[i]=count[i]=1(两个表都初始化为1）
④填表顺序：从左往右。
⑤返回值：通过小贪心的策略从左往右扫描时找最大值的同时，也更新最大值的个数。

class Solution 
{
public:
    int findNumberOfLIS(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> len(n, 1), count(n, 1);

        int retlen = 1, retcount = 1;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i])
                {
                    if(len[j] + 1 == len[i]) count[i] += count[j];
                    else if(len[j] + 1 > len[i]) len[i] = len[j] + 1, count[i] = count[j];
                }
            }
            if(retlen == len[i]) retcount += count[i];
            else if(retlen < len[i]) retlen = len[i], retcount = count[i];
        }
        return retcount;
    }
};

30、673. 最长递增子序列的个数
①状态表示：（先预处理：按照第一个元素排序即可）
dp[i]表示:以i位置的元素为结尾的所有数对链中，最长数对链的长度。
②状态转移方程：
长度为1：dp[i]=1
长度大于1：if(p[j][1]<p[i][0]) dp[i]=max(dp[j]+1)
③初始化：表中元素都初始化为1
④填表顺序：从左往右。
⑤返回值：dp表中的最大值。

class Solution 
{
public:
    int findLongestChain(vector<vector<int>>& pairs) 
    {
        sort(pairs.begin(), pairs.end());
        int n = pairs.size();
        vector<int> dp(n, 1);

        int ret = 1;

        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(pairs[j][1]<pairs[i][0]) dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

31、1218. 最长定差子序列
①状态表示：
dp[i]表示:以i位置的元素为结尾的所有子序列里面，最长等差子序列的长度。
②状态转移方程：
b不存在：1
b存在：最后一个：dp[j]+1
优化：将元素+dp[j]的值，绑定放在哈希表中。直接在哈希表中，做动态规划。
③初始化：hash[arr[0]]=1
④填表顺序：从左往右。
⑤返回值：dp表中的最大值。

class Solution 
{
public:
    int longestSubsequence(vector<int>& arr, int difference) 
    {
        unordered_map<int, int> hash;
        hash[arr[0]] = 1;

        int ret = 1;
        for(int i = 1; i < arr.size(); i++)
        {
            hash[arr[i]] = hash[arr[i] - difference] + 1;
            ret = max(ret, hash[arr[i]]);
        }
        return ret;
    }
};

32、1218. 最长定差子序列①状态表示：
dp[i]表示:以i位置的元素为结尾的所有子序列中，最长斐波那契子序列的长度。×
dp[i][j]表示:以i位置以及j位置为结尾的所有子序列里面，最长斐波那契子序列的长度。
②状态转移方程：nums[i]=b;nums[j]=c;nums[k]=a;
a存在，且a<b：dp[i][j]=dp[k][j]+1
a存在，且b<a<c / a不存在：dp[i][j]=2
优化：将数组中所有元素与它们的下标绑定，存在哈希表中。直接在哈希表中，做动态规划。
③初始化：表里面所有的值都初始化为2。
④填表顺序：从上往下。
⑤返回值：dp表中的最大值。ret<3?0:ret

class Solution 
{
public:
    int lenLongestFibSubseq(vector<int>& arr) 
    {
        int n = arr.size();
        // 优化
        unordered_map<int, int> hash;
        for(int i = 0; i < n; i++) hash[arr[i]] = i;

        int ret = 2;
        vector<vector<int>> dp(n, vector(n, 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.count(a)) dp[i][j] = dp[hash[a]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
        }
        return ret < 3 ? 0 : ret;
    }
};

33、1027. 最长等差数列
①状态表示：
dp[i]表示:以i位置的元素为结尾的所有子序列中，最长等差序列的长度。×
dp[i][j]表示:以i位置以及j位置为结尾的所有子序列里面，最长等差序列的长度。
②状态转移方程：nums[i]=b;nums[j]=c;nums[k]=a;
a存在，且a<b：dp[i][j]=dp[k][j]+1
a存在，且b<a<c / a不存在：dp[i][j]=2
优化：
法一：将数组中所有元素与它们的下标绑定<元素，下标数组>，存在哈希表中。直接在哈希表中，做动态规划。(可行但超时）
法二：一边dp，一边保存离它最近的下标。<元素，下标>
③初始化：dp表中所有的值都初始化为2。
④填表顺序:
法一：先固定最后一个数，再枚举倒数第二个数（无法保存下标）
法二：先固定倒数第二个数，再枚举最后一个数。
选第二种填表方式，当i位置填完之后，将i位置的值放入哈希表中即可。
⑤返回值：dp表中的最大值。

class Solution 
{
public:
    int longestArithSeqLength(vector<int>& nums) 
    {
        // 优化
        unordered_map<int,int> hash;
        hash[nums[0]] = 0;

        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 2)); // 创建dp表 + 初始化

        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.count(a))
                    dp[i][j] = dp[hash[a]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
            hash[nums[i]] = i;
        }
        return ret;
    }
};

33、446.等差数列划分 II - 子序列
①状态表示：
dp[i]表示:以i位置的元素为结尾的所有子序列中，等差子序列的个数。（×只知道子序列的个数，但不能确定一个具体的子序列）
dp[i][j]表示:以i位置以及j位置为结尾的所有子序列中，等差子序列的个数。
②状态转移方程：nums[i]=b;nums[j]=c;nums[kx]=a;
a存在，且kx<i：dp[i][j]=dp[kx][i]+1
dp[i][j]+=dp[kx][i]+1
优化：将<元素，下标数组>绑定在一起，存在哈希表中。
③初始化：dp表中所有的值都初始化为0。
④填表顺序:先固定最后一个数，再枚举倒数第二个数
⑤返回值：dp表中的所有元素的和。

class Solution 
{
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        int n = nums.size();
        // 优化
        unordered_map<long long, vector<int>> hash;
        for(int i = 0; i < n; i++) hash[nums[i]].push_back(i);

        vector<vector<int>> dp(n, vector<int>(n)); // 创建dp表 + 初始化

        int sum = 0;
        for(int j = 2; j < n; j++) // 固定倒数第二个数
        {
            for(int i = 1; i < j; i++) // 枚举倒数第一个数
            {
                long long a = (long long)2 * nums[i] - nums[j];
                if(hash.count(a))
                {
                    for(auto k : hash[a])
                    {
                        if(k < i) dp[i][j] +=dp[k][i] + 1;
                    }
                }
                sum += dp[i][j];
            }
        }
        return sum;
    }
};

阅读全部

相关推荐

  1. 算法篇：动态规划I

    2024-01-09 08:18:03       30 阅读

  2. 算法篇：动态规划II

    2024-01-09 08:18:03       33 阅读

  8. 动态规划算法介绍

    2024-01-09 08:18:03       68 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-01-09 08:18:03       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-01-09 08:18:03       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-01-09 08:18:03       19 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-01-09 08:18:03       20 阅读

热门阅读

  1. 数据库常见的面试题

    2024-01-09 08:18:03       32 阅读

  2. 什么是k8s和声明式编程？

    2024-01-09 08:18:03       42 阅读

  12. 【初识微服务Cloud-预习】

    2024-01-09 08:18:03       36 阅读

  13. RestTemplate发送https请求

    2024-01-09 08:18:03       39 阅读

  14. 安全防御之漏洞扫描技术

    2024-01-09 08:18:03       40 阅读

  15. 安卓之视频智能字幕的应用场景以及各种技术优劣分析

    2024-01-09 08:18:03       35 阅读

  18. Protobuf 反射技术简介

    2024-01-09 08:18:03       37 阅读

  19. ffmpeg api-band-test.c 讲解

    2024-01-09 08:18:03       31 阅读

  20. ros2 ubuntu 20.04 安装 foxy

    2024-01-09 08:18:03       38 阅读

  24. 解决递归问题的六种方法

    2024-01-09 08:18:03       46 阅读

  25. 2024.1.8

    2024-01-09 08:18:03       37 阅读

  26. 273. Integer to English Words

    2024-01-09 08:18:03       36 阅读

  28. 【Python机器学习】理论知识：决策树

    2024-01-09 08:18:03       39 阅读