DP专题

749 · 约翰的后花园

描述

约翰想在他家后面的空地上建一个后花园，现在有两种砖，一种3 dm的高度，7 dm的高度。约翰想围成x dm的墙。如果约翰能做到，输出YES，否则输出NO。

X是一个整数，取值范围为 [3, 1000]。

样例

样例 1:

输入 : x = 10 输出 : "YES" #### 解释： x = 3 + 7 : 即需要1匹3 dm高度的砖和1匹7 dm 高度的砖。 #### 样例 2:

输入 : x = 5 输出 : "NO" #### 解释：不能用高度为3 dm的砖和高度为7 dm的砖砌成 5 dm的墙。

Code1

240128

20 ms 时间消耗 · 1.75 MB 空间消耗 · 您的提交打败了 99.20 % 的提交

class Solution {
public:
    /**
     * @param x: the wall's height
     * @return: YES or NO
     */
    string isBuild(int x) {
        int seven=x/7;
        int three=(x-seven*7)/3;
        while(seven>=0){
            if(seven*7+three*3==x){
                return "YES";
            }
            seven--;
            three=(x-seven*7)/3;
        }
        return "NO";
    }
};

Code2

240128

21 ms 时间消耗 · 3.16 MB 空间消耗 · 您的提交打败了 86.40 % 的提交

class Solution {
public:
    /**
     * @param x: the wall's height
     * @return: YES or NO
     */
    string isBuild(int x) {
        bool able[x+1]={false,false,false,true,false,false,true,true};
        for(int i=8;i<=x;i++){
            if(able[i-3] || able[i-7])
                able[i]=true;
            else 
                able[i]=false;
        }
        if(able[x])
            return "YES";
        else
            return "NO";
    }
};

1025. 除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 \(n\) 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 \(x\)，满足 \(0 < x < n\) 且 \(n % x == 0\) 。
用 \(n - x\) 替换黑板上的数字 \(n\) 。
如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

示例 1：

输入：n = 2

输出：true

解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

输入：n = 3

输出：false

解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

提示：

\(1 <= n <= 1000\)

Code

class Solution {
public:
    bool isprime(int n){
        if(n<=1)    return false;
        if(n==2)    return true;
        if(n%2==0)  return false;
        for(int i=3;i<=sqrt(n);i++){
            if(n%i==0)  return false;
        }
        return true;
    }
    bool divisorGame(int n) {
        bool dp[n+1];
        memset(dp,false,sizeof(dp));
        for(int i=1;i<=n;i++){
            if(dp[i]==true)    continue;
            int x=1;
            while(i+x<=n){
                if((i+x)%x==0)  dp[i+x]=true;
                x++;
            }
        }
        // bool flag=false; //true轮到bob操作
        // int alice=n,bob=n;
        // while(n!=1){
        //     if(isprime(n)){
        //         flag=!flag;
        //         n--;
        //         continue;
        //     }
        //     for(int i=2;i<n;i++){
        //         if(n%i==0){
        //             n-=n/i;
        //             flag=!flag;
        //             break;
        //         }
        //     }
        // }
        return dp[n];
    }
};

LCP 07. 传递信息

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。每轮信息必须需要传递给另一个人，且信息可重复经过同一个人给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

示例 1：

输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3

输出：3

解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

示例 2：

输入：n = 3, relation = [[0,2],[2,1]], k = 2

输出：0

解释：信息不能从小 A 处经过 2 轮传递到编号 2

限制：

\(2 <= n <= 10\)
\(1 <= k <= 5\)
\(1 <= relation.length <= 90, 且 relation[i].length == 2\)
\(0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]\)

Code

class Solution {
public:
    int numWays(int n, vector<vector<int>>& relation, int k) {
        vector<set<int>> relations(n);
        for(auto &p:relation){
            relations[p[0]].insert(p[1]);
        }
        vector<vector<int>> v(k+1,vector<int>(n,0));
        for(auto &p:relations[0]){
            v[1][p]=1;
        }
        for(int i=2;i<=k;i++){
            for(int j=0;j<n;j++){
                if(v[i-1][j]!=0){
                    for(auto &p:relations[j]){
                        v[i][p]+=v[i-1][j];
                    }
                }
            }
        }
        // set<int> pre;
        // pre.insert(0);
        // set<int> now;
        // while(k--){
        //     for(auto &k:relation){
        //         if(pre.find(k[0]])!=pre.end()){
        //             now.insert(k[1]);
        //         }
        //     }
        //     pre=now;
        //     now.clear();
        // }
        return v[k][n-1];
    }
};

LCR 003. 比特位计数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1:

输入: n = 2

输出: [0,1,1]

解释:

0 --> 0
1 --> 1
2 --> 10

示例 2:

输入: n = 5

输出: [0,1,1,2,1,2]

解释:

0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

说明 :

0 <= n <= 105

进阶:

给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？

要求算法的空间复杂度为 O(n) 。

你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。

Code

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> v(n+1,0);
        int power=1;
        for(int i=1;i<=n;i++){
            if(i==power){
                power*=2;
            }
            if(i<power){
                v[i]=v[i-power/2]+1;
            }
        }
        return v;
    }
};

面试题 05.03. 翻转数位

240211

给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。

示例 1：

输入: num = 1775(110111011112) 输出: 8 ### 示例 2：

输入: num = 7(01112) 输出: 4

Code

class Solution {
public:
    int reverseBits(int num) {
        if(num==-1) return 32;
        vector<int> v(32);
        int mx=0;
        for(int i=0;i<32;i++){
            v[i]=num&1;
            num>>=1;
        }
        for(int i=0;i<v.size();i++){
            int cnt=1;
            if(v[i]==0){
                int cur=i-1;
                while(cur>=0 && v[cur]==1){
                    cnt++;
                    cur--;
                }
                cur=i+1;
                while(cur<v.size() && v[cur]==1){
                    cnt++;
                    cur++;
                }
                mx=mx>cnt?mx:cnt;
            }
        }
        return mx;
    }
};

面试题 16.17. 连续数列

240211

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

输入： [-2,1,-3,4,-1,2,1,-5,4]

输出： 6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶：

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

Code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre=0,mx=0x80000001;
        for(auto &k:nums){
            pre=max(pre+k,k);
            mx=max(pre,mx);
        }
        return mx;
    }
};

面试题 17.16. 按摩师

240211

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

示例 1：

输入： [1,2,3,1]

输出： 4

解释：选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

输入： [2,7,9,3,1]

输出： 12

解释：选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

示例 3：

输入： [2,1,4,5,3,1,1,3]

输出： 12

解释：选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

Code

class Solution {
public:
    int massage(vector<int>& nums) {
        int n=nums.size();
        if(n==0)    return 0;
        vector<pair<int,int>> v(n);
        v[0]=make_pair(0,nums[0]);
        for(int i=1;i<n;i++){
            v[i].first=max(v[i-1].first,v[i-1].second);
            v[i].second=v[i-1].first+nums[i];
        }
        return max(v.back().first,v.back().second);
        // int pre_get=0,pre_notget=0,now=0;
        // for(int &k:nums){
        //     if(pre_get>pre_notget+k){ //不选
        //         now=pre_get;
        //         pre_get=pre_notget+k;
        //         pre_notget=now;
        //     }else{ //选
        //         now=pre_notget+k;
        //         pre_notget=pre_get;
        //         pre_get=now;
        //     }
        // }
        // return now;
    }
};

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶

示例 2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶

Code

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

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

Code

class Solution {
public:
    int fib(int n) {
        if(n==0)    return 0;
        if(n==1)    return 1;
        int a=0,b=1,c;
        int count=1;
        while(count<n){
            c=a+b;
            a=b;
            b=c;
            count++;
        }
        return c;
    }
};

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

提示：

0 <= n <= 37
答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

Code

class Solution {
public:
    int tribonacci(int n) {
        if(n==0)    return 0;
        if(n==1)    return 1;
        if(n==2)    return 1;
        int a=0,b=1,c=1,d;
        n-=2;
        while(n--){
            d=a+b+c;
            a=b,b=c,c=d;
        }
        return c;
    }
};

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

2 <= cost.length <= 1000
0 <= cost[i] <= 999

Code

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int a=0,b=0,c;
        for(int i=1;i<cost.size();i++){
            c=min(a+cost[i-1],b+cost[i]);
            a=b,b=c;
        }
        return b;
    }
};

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 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

Code

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1)  return nums[0];
        if(nums.size()==2)  return max(nums[0],nums[1]);
        if(nums.size()==3)  return max(nums[0]+nums[2],nums[1]);
        vector<int> dp(nums.size());
        dp[0]=nums[0],dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++){
            if(dp[i-1]>dp[i-2]+nums[i]){
                dp[i]=dp[i-1];
            }else{
                dp[i]=dp[i-2]+nums[i];
            }
        }
        return max(dp[dp.size()-1],dp[dp.size()-2]);
    }
};

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

Code

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int num[10010];
        memset(num,0,sizeof(num));
        for(int &i:nums){
            num[i]++;
        }
        int dp[10010][2];
        dp[1][0]=0;
        dp[1][1]=num[1]*1;
        dp[2][0]=num[1]*1;
        dp[2][1]=num[2]*2;
        for(int i=3;i<10010;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=max({dp[i-2][0],dp[i-1][0]})+num[i]*i;
        }
        return max(dp[10009][1],dp[10009][0]);
    }
};

62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

Code

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            dp[i][0]=1;
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

64. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

Code

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int dp[m][n];
        memset(dp,0,sizeof(dp));
        dp[0][0]=grid[0][0];
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for(int j=1;j<m;j++){
            dp[j][0]=dp[j-1][0]+grid[j][0];
            for(int i=1;i<n;i++){
                dp[j][i]=min(dp[j-1][i],dp[j][i-1])+grid[j][i];
            }
        }
        return dp[m-1][n-1];
    }
};

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

Code

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size(),n=obstacleGrid[0].size();
        int dp[m][n];
        if(obstacleGrid[0][0])  dp[0][0]=0;
        else dp[0][0]=1;
        for(int j=1;j<n;j++){
            if(obstacleGrid[0][j]) dp[0][j]=0;
            else dp[0][j]=dp[0][j-1];
        }
        for(int i=1;i<m;i++){
            if(obstacleGrid[i][0]) dp[i][0]=0;
            else dp[i][0]=dp[i-1][0];
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]) dp[i][j]=0;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

Code

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> v(1);
        v[0]=triangle[0][0];
        int n=triangle.size();
        for(int i=1;i<n;i++){
            v.emplace_back(v.back()+triangle[i].back());
            for(int j=v.size()-2;j>0;j--){
                v[j]=min(v[j],v[j-1])+triangle[i][j];
            }
            v.front()+=triangle[i].front();
        }
        int minimum=0x3f3f3f3f;
        for(int &i:v){
            minimum=min(minimum,i);
        }
        return minimum;
    }
};

931. 下降路径最小和

给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径

示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径

提示：

n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

Code

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n=matrix.size();
        if(n==1)    return matrix[0][0];
        vector<int> pre=matrix[0],cur(n);
        for(int i=1;i<n;i++){
            cur[0]=min(pre[0],pre[1])+matrix[i][0];
            for(int j=1;j<n-1;j++){
                cur[j]=min({pre[j-1],pre[j],pre[j+1]})+matrix[i][j];
            }
            cur[n-1]=min(pre[n-2],pre[n-1])+matrix[i][n-1];
            pre=cur;
        }
        int minimum=0x3f3f3f3f;
        for(int &i:pre){
            minimum=min(minimum,i);
        }
        return minimum;
    }
};

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

Code

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        vector<vector<char>> vv=matrix;
        int m=vv.size(),n=vv[0].size();
        int size=1;
        bool flag=false;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(vv[i][j]=='1'){
                    size=1;
                    flag=true;
                }
            }
        }
        if(!flag)   return 0;
        while(m>1 && n>1){
            flag=false;
            for(int i=0;i<m-1;i++){
                for(int j=0;j<n-1;j++){
                    if(vv[i][j]=='1' && vv[i+1][j]=='1' && vv[i][j+1]=='1' && vv[i+1][j+1]=='1'){
                        flag=true;
                    }else{
                        vv[i][j]='0';
                    }
                }
            }
            if(flag==false) break;
            size++;
            m--,n--;
            vv.resize(m);
            for(auto &i:vv){
                i.resize(n);
            }
        }
        return size*size;
    }
};

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

Code

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.length();
        vector<int> v(len,1);
        string res2;
        bool flag=false;
        for(int i=0;i<len-1;i++){
            if(s[i]==s[i+1]){
                v[i]=2;
                res2=s.substr(i,2);
                flag=true;
            }else v[i]=0;
        }
        int size=4;
        while(flag && size<=len){
            flag=false;
            for(int i=0;i<len-size+1;i++){
                if(v[i+1]==size-2 && s[i]==s[i+size-1]){
                    v[i]=size;
                    flag=true;
                    res2=s.substr(i,size);
                }else v[i]=0;
            }
            size+=2;
        }
        string res1=s.substr(0,1);
        v.clear();
        v.resize(len,1);
        flag=true;
        size=3;
        while(flag && size<=len){
            flag=false;
            for(int i=0;i<len-size+1;i++){
                if(v[i+1]==size-2 && s[i]==s[i+size-1]){
                    v[i]=size;
                    flag=true;
                    res1=s.substr(i,size);
                }else v[i]=0;
            }
            size+=2;
        }
        return (res1.size()>res2.size())?res1:res2;
    }
};

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

Code

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> us(wordDict.begin(),wordDict.end());
        int len=s.length();
        vector<bool> v(len+1,false);
        v[0]=true;
        for(int i=0;i<=len;i++){
            for(int j=0;j<i;j++){
                if(v[j] && us.find(s.substr(j,i-j))!=us.end()){
                    v[i]=true;
                    break;
                }
            }
        }
        return v[len];
    }
};

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

Code

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len=s.length();
        vector<vector<int>> dp(len,vector<int>(len,0));
        for(int i=0;i<len;i++){
            dp[i][i]=1;
        }
        for(int i=len-2;i>=0;i--){
            for(int j=i+1;j<len;j++){
                if(s[i]==s[j]){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
};

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

Code

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1=word1.length(),len2=word2.length();
        vector<vector<int>> dp(len2+1,vector<int>(len1+1));
        for(int i=0;i<=len1;i++){
            dp[0][i]=i;
        }
        for(int j=0;j<=len2;j++){
            dp[j][0]=j;
        }
        for(int i=1;i<=len2;i++){
            for(int j=1;j<=len1;j++){
                if(word2[i-1]==word1[j-1])  dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min({dp[i][j-1],dp[i-1][j-1],dp[i-1][j]})+1;
            }
        }
        return dp[len2][len1];
    }
};

712. 两个字符串的最小ASCII删除和

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

提示:

0 <= s1.length, s2.length <= 1000
s1 和 s2 由小写英文字母组成

Code

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m=s1.length(),n=s2.length();
        int dp[m+1][n+1];
        dp[0][0]=0;
        for(int i=1;i<=m;i++)   dp[i][0]=dp[i-1][0]+s1[i-1];
        for(int j=1;j<=n;j++)   dp[0][j]=dp[0][j-1]+s2[j-1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min({dp[i][j-1]+s2[j-1],dp[i-1][j]+s1[i-1],dp[i-1][j-1]+s1[i-1]+s2[j-1]});
            }
        }
        return dp[m][n];
    }
};

115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

Code

class Solution {
public:
    int numDistinct(string s, string t) {
        int m=s.length(),n=t.length();
        int dp[n+1][m+1];
        for(int i=1;i<=n;i++) dp[i][0]=0;
        for(int j=0;j<=m;j++) dp[0][j]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(t[i-1]==s[j-1])  dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%1000000007;
                else dp[i][j]=dp[i][j-1];
                // cout<<"s="<<s.substr(0,j)<<",t="<<t.substr(0,i)<<",dp="<<dp[i][j]<<endl;
            }
        }
        return dp[n][m]%1000000007;
    }
};

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

Code

// class Solution {
// public:
//     int lengthOfLIS(vector<int>& nums) {
//         int n=nums.size();
//         int dp[n][2];
//         dp[0][0]=0;
//         dp[0][1]=1;
//         for(int i=1;i<n;i++){
//             if(dp[i-1]<dp[i]){
//                 dp[i][1]=dp[i-1][1]+1;
//                 dp[i][0]=dp[i-1][1];
//             }else{
//                 int t=i-1;
//                 while(nums[t]>nums[i] && t>=0)  t--;
//                 dp[i][1]=dp[t][1]+1;
//                 dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
//             }
//             cout<<"dp["<<i<<"][0]="<<dp[i][0]<<",dp["<<i<<"][1]="<<dp[i][1]<<endl;
//         }
//         return max(dp[n-1][0],dp[n-1][1]);
//     }
// };

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,1);
        // memset(dp,1,sizeof(dp));
        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);
                }
            }
            // cout<<"i="<<i<<", [";
            // for(int i=0;i<n;i++)    cout<<dp[i]<<",";
            // cout<<"]"<<endl;
        }
        int MAX=0;
        for(int i=0;i<n;i++) MAX=max(MAX,dp[i]);
        return MAX;
    }
};

673. 最长递增子序列的个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意这个数列必须是严格递增的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

提示:

1 <= nums.length <= 2000
-106 <= nums[i] <= 106

Code

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size(),maxlen=0,count=0;
        vector<int> dp(n,1),counts(n,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(dp[j]+1>dp[i]){
                        dp[i]=dp[j]+1;
                        counts[i]=counts[j];
                    }else if(dp[j]+1==dp[i]){
                        counts[i]+=counts[j];
                    }
                }
            }
            if(dp[i]>maxlen){
                maxlen=dp[i];
                count=counts[i];
            }else if(dp[i]==maxlen){
                count+=counts[i];
            }
            // for(int j=0;j<i;j++){
            //     if(dp[i]-1==dp[j]){
            //         v[i]+=v[j];
            //     }
            // }
        }
        for(int i=0;i<n;i++) cout<<dp[i]<<" ";
        cout<<endl;
        for(int i=0;i<n;i++) cout<<counts[i]<<" ";
        cout<<endl;
        return count;

        // int count=1;
        // int MAX=0;
        // vector<int> v(n+1,0);
        // for(int i=0;i<n;i++){
        //     cout<<","<<dp[i];
        //     MAX=max(MAX,dp[i]);
        //     v[dp[i]]++;
        // }
        // for(int i=1;i<=MAX;i++){
        //     count*=v[i];
        // }
        // return count;

        // int MAX=-0x3f3f3f3f,count=0;
        // for(int i=0;i<n;i++){
        //     // cout<<","<<dp[i];
        //     if(dp[i]>MAX){
        //         MAX=dp[i];
        //         count=0;
        //     }else if(dp[i]==MAX){
        //         count++;
        //     }
        // }
        // return count;
    }
};

646. 最长数对链

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 1：

输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。

示例 2：

输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。

提示：

n == pairs.length
1 <= n <= 1000
-1000 <= lefti < righti <= 1000

Code

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end(),[&](vector<int> a,vector<int> b){
            if(a[0]==b[0])
                return a[1]<b[1];
            return a[0]<b[0];
        });
        int n=pairs.size();
        vector<int> dp(n,1);
        int MAX=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(pairs[i][0]>pairs[j][1]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            MAX=max(MAX,dp[i]);
        }
        return MAX;
    }
};

1218. 最长定差子序列

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1：

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

提示：

1 <= arr.length <= 105
-104 <= arr[i], difference <= 104

Code

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n=arr.size(),MAX=1;
        // vector<int> dp(n,1);
        unordered_map<int,int> um;
        for(int i=0;i<n;i++){
            if(um[arr[i]-difference]){
                um[arr[i]]=max(um[arr[i]],um[arr[i]-difference]+1);
                MAX=max(MAX,um[arr[i]]);
            }else{
                um[arr[i]]=1;
            }
            // for(int j=0;j<i;j++){
            //     if(arr[j]+difference==arr[i]){
            //         dp[i]=max(dp[i],dp[j]+1);
            //     }
            // }
            // MAX=max(MAX,dp[i]);
        }
        return MAX;
    }
};

1027. 最长等差数列

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

示例 2：

输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：

输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：

2 <= nums.length <= 1000
0 <= nums[i] <= 500

Code

class Solution {
public:
    struct node{
        int diff,last,len;
    };
    int longestArithSeqLength(vector<int>& nums) {
        int n=nums.size(),MAX=0;
        vector<vector<int>> dp(n,vector<int>(1001,1));
        // dp[0].clear();
        // dp[0].resize(1001,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                int diff=nums[i]-nums[j]+500;
                dp[i][diff]=max(dp[i][diff],dp[j][diff]+1);
                MAX=max(MAX,dp[i][diff]);
            }
        }
        return MAX;
    }
};

354. 俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

提示：

1 <= envelopes.length <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105

Code

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n=envelopes.size(),MAX=1;
        sort(envelopes.begin(),envelopes.end(),[&](vector<int>a,vector<int>b){
            if(a[0]==b[0])
                return a[1]>b[1];
            return a[0]<b[0];
        });
        vector<int> dp;
        for(auto& envelope:envelopes){
            int height=envelope[1];
            auto it=lower_bound(dp.begin(),dp.end(),height);
            if(it==dp.end()){
                dp.emplace_back(height);
            }else{
                *it=height;
            }
        }
        return dp.size();
    }
};

Code_Failure

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n=envelopes.size(),MAX=1;
        sort(envelopes.begin(),envelopes.end(),[&](vector<int>a,vector<int>b){
            if(a[0]==b[0])
                return a[1]>b[1];
            return a[0]<b[0];
        });
        vector<int> dp(n,1);
        for(int i=1;i<n;i++){
            int j=i-1;
            while(j>=0 && envelopes[j][0]==envelopes[i][0]) j--;
            while(j>=0){
                if(envelopes[j][1]<envelopes[i][1]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
                if(dp[i]>MAX) break;
                j--;

                // auto cur=upper_bound(envelopes.begin(),envelopes.begin()+j,envelopes[i]);
                // if(cur!=envelopes.begin()+j){
                //     int x=cur-envelopes.begin();
                //     dp[i]=max(dp[i],dp[x]);
                // }

                // if(envelopes[j][0]<envelopes[i][0] && envelopes[j][1]<envelopes[i][1]){
                //     dp[i]=max(dp[i],dp[j]+1);
                //     break;
                // }
            }
            MAX=max(MAX,dp[i]);
            // for(int j=i-1;j>=0;j--){
            //     if(dp[j+1]<dp[j]){
            //         swap(dp[j+1],dp[j]);
            //         swap(envelopes[j+1],envelopes[j]);
            //     }
            // }
        }
        return MAX;
    }
};

1964. 找出到每个位置为止最长的有效障碍赛跑路线

你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。

对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：

你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
在这条路线中，必须包含第 i 个障碍。
你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍相同或者更高。

返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

示例 1：

输入：obstacles = [1,2,3,2]
输出：[1,2,3,3]
解释：每个位置的最长有效障碍路线是：
- i = 0: [1], [1] 长度为 1
- i = 1: [1,2], [1,2] 长度为 2
- i = 2: [1,2,3], [1,2,3] 长度为 3
- i = 3: [1,2,3,2], [1,2,2] 长度为 3

示例 2：

输入：obstacles = [2,2,1]
输出：[1,2,1]
解释：每个位置的最长有效障碍路线是：
- i = 0: [2], [2] 长度为 1
- i = 1: [2,2], [2,2] 长度为 2
- i = 2: [2,2,1], [1] 长度为 1

示例 3：

输入：obstacles = [3,1,5,6,4,2]
输出：[1,1,2,3,2,2]
解释：每个位置的最长有效障碍路线是：
- i = 0: [3], [3] 长度为 1
- i = 1: [3,1], [1] 长度为 1
- i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线
- i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线
- i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线
- i = 5: [3,1,5,6,4,2], [1,2] 长度为 2

提示：

n == obstacles.length
1 <= n <= 105
1 <= obstacles[i] <= 107

Code

240226

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        int n=obstacles.size();
        vector<int> dp(n,1),tails;
        for(int i=0;i<n;i++){
            auto it=upper_bound(tails.begin(),tails.end(),obstacles[i]);
            int length=it-tails.begin();
            if(it==tails.end()){
                tails.emplace_back(obstacles[i]);
            }else{
                *it=obstacles[i];
            }
            dp[i]=length+1;

            // Debug
            cout<<"DP: ";
            for(auto &k:dp){
                cout<<k<<" ";
            }
            cout<<endl;
            cout<<"Tails: ";
            for(auto &k:tails){
                cout<<k<<" ";
            }
            cout<<endl;
            cout<<endl;

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

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    Solution sol;
    sol.longestObstacleCourseAtEachPosition(v);
    return 0;
}

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

Code

240226

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.length();
        int m=text2.length();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(text1[i-1]==text2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
};

1035. 不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2：

输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

示例 3：

输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

提示：

1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

Code

240226

本质还是最长公共子序列

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n=nums1.size();
        int m=nums2.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
};

1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1：

输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3：

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

提示：

1 <= s.length <= 500
s 中所有字符都是小写字母。

Code

//EOF

309. 买卖股票的最佳时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

提示：

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

Code

240226

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(3,0));
        dp[0][0]=-prices[0];//持有股票
        dp[0][1]=0;//在空窗期
        dp[0][2]=0; //不在空窗期
        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][2]-prices[i],dp[i-1][0]);
            dp[i][1]=dp[i-1][0]+prices[i];
            dp[i][2]=max(dp[i-1][1],dp[i-1][2]);
        }
        return max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});

        // vector<vector<pair<int,int>>> dp(3,vector<pair<int,int>>(n+1,make_pair(-1,-1)));
        // dp[0][0]=make_pair(0,-1); //在之前可以不操作
        // dp[1][0]=make_pair(-1,-1);//在之前没有买过
        // dp[2][0]=make_pair(0,-1); //在之前可以卖过
        // for(int i=1;i<=n;i++){
        //     if(dp[1][i-1].first==-1){
        //         dp[0][i]=
        //     }
        // }
        
    }
};

714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104

Code

240226

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2,0));
        dp[0][0]=-prices[0];//持有股票
        dp[0][1]=0;//不持有股票
        for(int i=1;i<n;i++){
            dp[i][1]=max(dp[i-1][0]+prices[i]-fee,dp[i-1][1]);
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
        }
        return max(dp[n-1][0],dp[n-1][1]);
    }
};

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 105

Code

240226

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int hold1=-0x3f3f3f3f,sold1=-0x3f3f3f3f,hold2=-0x3f3f3f3f,sold2=-0x3f3f3f3f;
        for(int i=0;i<n;i++){
            sold2=max(sold2,hold2+prices[i]);
            hold2=max(hold2,sold1-prices[i]);
            sold1=max(sold1,hold1+prices[i]);
            hold1=max(hold1,-prices[i]);
        }
        return max({hold1,sold1,hold2,sold2,0});
    }
};

188. 买卖股票的最佳时机 IV

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

Code

240226

class Solution {
public:
int maxProfit(int k,vector<int>& prices) {
        int n=prices.size(),MAX=0;
        vector<pair<int,int>> dp(k,make_pair(-0x3f3f3f3f,-0x3f3f3f3f));
        for(int i=0;i<n;i++){
            for(int j=k-1;j>0;j--){
                dp[j].second=max(dp[j].second,dp[j].first+prices[i]);
                dp[j].first=max(dp[j].first,dp[j-1].second-prices[i]);
                MAX=max({MAX,dp[j].second,dp[j].first});
            }
            dp[0].second=max(dp[0].second,dp[0].first+prices[i]);
            dp[0].first=max(dp[0].first,-prices[i]);
            MAX=max({MAX,dp[0].second,dp[0].first});
        }
        return MAX;
    }
};

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

Code

240226

class Solution {
public:
int numTrees(int n) {
        vector<int> v(n+1,0);
        v[0]=1,v[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=0;j<i;j++){
                v[i]+=v[j]*v[i-j-1];
            }
        }
        return v[n];
    }
};

95. 不同的二叉搜索树 II

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 8

Code

240226

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> gen(int begin,int end){
        // if(begin>end)   return {};
        vector<TreeNode*> v;
        if(begin>end){
            v.emplace_back(nullptr);
            return v;
        }
        for(int i=begin;i<=end;i++){
            vector<TreeNode*> fronts=gen(begin,i-1);
            vector<TreeNode*> backs=gen(i+1,end);
            for(auto &front:fronts){
                for(auto &back:backs){
                    v.emplace_back(new TreeNode(i,front,back));
                }
            }
        }
        return v;
    }

    vector<TreeNode*> generateTrees(int n) {
        return gen(1,n);
    }
};

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104

Code1

240227

超时

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int solve(TreeNode* root,int choice){
        // int l0,l1,r0,r1;
        // l0=(root->left)?solve(root->left,0):0;
        // l1=(root->left)?solve(root->left,1):0;
        // r0=(root->right)?solve(root->right,0):0;
        // r1=(root->right)?solve(root->right,1):0;
        // if(choice) return l0+r0+root->val;
        // else return max(l0,l1)+max(r0,r1);
        if(choice){
            return ((root->left)?solve(root->left,0):0)+((root->right)?solve(root->right,0):0)+root->val;
        }else{
            return max(((root->left)?solve(root->left,0):0),((root->left)?solve(root->left,1):0))
                +max(((root->right)?solve(root->right,0):0),((root->right)?solve(root->right,1):0));
        }
    }
    int rob(TreeNode* root) {
        return max(solve(root,0),solve(root,1));
    }
};

Code2

240227

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(): val(0),left(nullptr),right(nullptr){}
    TreeNode(int x): val(x),left(nullptr),right(nullptr){}
    TreeNode(int x,TreeNode* left,TreeNode* right): val(x),left(left),right(right){}
};

class Solution{
    public:
    unordered_map<TreeNode*,pair<int,int>> ump;
    pair<int,int> solve(TreeNode* root){
        if(root==NULL)  return make_pair(0,0);
        if(ump.find(root->left)==ump.end()){
            ump[root->left]=solve(root->left);
        }
        if(ump.find(root->right)==ump.end()){
            ump[root->right]=solve(root->right);
        }
        pair<int,int> p;
        p.first=max(ump[root->left].first,ump[root->left].second)
            +max(ump[root->right].first,ump[root->right].second);
        p.second=ump[root->left].first+ump[root->right].first+root->val;
        return p;
    }
    int rob(TreeNode* root){
        return max(solve(root).first,solve(root).second);
    }
};

124. 二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

Code1

240227

现在仅能够处理正数

class Solution{
    public:
    unordered_map<TreeNode*,pair<int,int>> ump;
    pair<int,int> solve(TreeNode* root){
        if(root==NULL)  return make_pair(0,0);
        if(!root->left && !root->right) return make_pair(0,root->val);
        if(ump.find(root->left)==ump.end()){
            ump[root->left]=solve(root->left);
        }
        if(ump.find(root->right)==ump.end()){
            ump[root->right]=solve(root->right);
        }
        pair<int,int> p;
        p.first=max({   ump[root->left].first, //不包含本节点
                        ump[root->left].second,
                        ump[root->right].first,
                        ump[root->right].second });
        p.second=max(0,ump[root->left].second) //包含本节点
                +max(0,ump[root->right].second)+root->val;
        return p;
    }
    int maxPathSum(TreeNode* root){
        pair<int,int> p=solve(root);
        return max(p.first,p.second);
    }
};

Code2

240228

class Solution{
    public:
    struct node{
        int first,second,third;
        node(int a,int b,int c): first(a),second(b),third(c){}
        node(): first(INT_MIN),second(INT_MIN),third(INT_MIN){}
    };
    unordered_map<TreeNode*,node> ump;
    node solve(TreeNode* root){
        if(root==NULL)  return node();
        if(!root->left && !root->right) return node(INT_MIN,root->val,root->val);
        if(ump.find(root->left)==ump.end()){
            ump[root->left]=solve(root->left);
        }
        if(ump.find(root->right)==ump.end()){
            ump[root->right]=solve(root->right);
        }
        Solution::node p;
        p.first=max({   ump[root->left].first, //不包含本节点
                        ump[root->left].second,
                        ump[root->left].third,
                        ump[root->right].first,
                        ump[root->right].second,
                        ump[root->right].third,
                        INT_MIN });
        p.second=max({0,ump[root->left].second,ump[root->right].second})+root->val; //包含本节点，作为根节点
        p.third=max(0,ump[root->left].second)+max(0,ump[root->right].second)+root->val; //本节点作为路径
        // cout<<root->val<<" "<<p.first<<" "<<p.second<<endl;
        return p;
    }
    int maxPathSum(TreeNode* root){
        node pl=solve(root->left);
        node pr=solve(root->right);
        node p;
        p.first=max({   pl.first, //不包含本节点
                        pl.second,
                        pl.third,
                        pr.first,
                        pr.second,
                        pr.third,
                        INT_MIN });
        p.second=max(0,pl.second)+max(0,pr.second)+root->val; //包含本节点
        return max(p.first,p.second);
    }
};

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

Code

240228

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,0x3f3f3f3f);
        dp[0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=sqrt(i);j++){
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

提示：

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000

Code

240228

class Solution {
public:
    // int change(int amount, vector<int>& coins) {
    //     if(coins.size()==0) return 0;
    //     sort(coins.begin(),coins.end());
    //     if(amount<coins[0]) return 0;
    //     vector<int> dp(amount+1,0);
    //     dp[coins[0]]=1;
    //     dp[0]=1;
    //     for(int i=coins[0]+1;i<=amount;i++){
    //         for(int &coin:coins){
    //             if(i-coin>=0){
    //                 dp[i]+=dp[i-coin];
    //             }
    //         }
    //     }
    //     return dp[amount];
    // }
    int change(int amount, vector<int>& coins){
        vector<int> dp(amount+1,0);
        dp[0]=1;
        sort(coins.begin(),coins.end());
        for(int &coin:coins){
            for(int i=coin;i<=amount;i++){
                dp[i]+=dp[i-coin];
            }
        }
        return dp[amount];
    }
};

Code-Python

240325

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        coins.sort()
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for i in range(coin,amount+1):
                dp[i] += dp[i-coin]
        return dp[amount]

377. 组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

Code1

240228

超时

class Solution {
public:
    int cnt;
    vector<int> v;
    void solve(int target){
        for(int &k:v){
            if(target==k) cnt++;
            else if(target-k>0) solve(target-k);
            else break;
        }
    }
    int combinationSum4(vector<int>& nums, int target) {
        v=nums;
        sort(v.begin(),v.end());
        cnt=0;
        solve(target);
        return cnt;
    }
};

Code2

240228

注意加上dp[i-num]<INT_MAX-dp[i]，因为题目中说了答案在int32内。试过不加要爆int，longlong都会爆。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1,0);
        sort(nums.begin(),nums.end());
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int num:nums){
                if(i>=num && dp[i-num]<INT_MAX-dp[i]){
                    dp[i]+=dp[i-num];
                }else break;
            }
        }
        return dp[target];
    }
};

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

Code1

240228

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<vector<int>>> dp(strs.size()+1,vector<vector<int>>(m+1,vector<int>(n+1,0)));
        for(int i=1;i<=strs.size();i++){
            int cnt0=0,cnt1=0;
            for(auto &k:strs[i-1]){
                if(k=='0') cnt0++;
                else cnt1++;
            }
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){
                    if(j>=cnt0 && k>=cnt1)
                        dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-cnt0][k-cnt1]+1);
                    else dp[i][j][k]=dp[i-1][j][k];
                }
            }
            // DEBUG
            // cout<<"cnt0="<<cnt0<<",cnt1="<<cnt1<<endl;
            // for(int j=1;j<=m;j++){
            //     for(int k=1;k<=n;k++){
            //         cout<<dp[i][j][k]<<" ";
            //     }
            //     cout<<endl;
            // }
            // cout<<endl;
        }
        return dp[strs.size()][m][n];
    }
};

Code2

240228

优化空间

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> pre(m+1,vector<int>(n+1,0));
        vector<vector<int>> now=pre;
        for(string &str:strs){
            int cnt0=0,cnt1=0;
            for(auto &ch:str){
                if(ch=='0') cnt0++;
                else cnt1++;
            }
            for(int i=0;i<=m;i++){
                for(int j=0;j<=n;j++){
                    if(i>=cnt0 && j>=cnt1)
                        now[i][j]=max(pre[i][j],pre[i-cnt0][j-cnt1]+1);
                    else now[i][j]=pre[i][j];
                }
            }
            swap(pre,now);
        }
        return pre[m][n];
    }
};

Code3

240228

再次优化

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(string &str:strs){
            int cnt0=0,cnt1=0;
            for(char &ch:str){
                if(ch=='0') cnt0++;
                else cnt1++;
            }
            for(int i=m;i>=cnt0;i--){
                for(int j=n;j>=cnt1;j--){
                    dp[i][j]=max(dp[i][j],dp[i-cnt0][j-cnt1]+1);
                }
            }
        }
        return dp[m][n];
    }
};

2140. 解决智力问题

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择解决或者跳过操作。解决问题 i 将让你获得 pointsi 的分数，但是你将无法解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

比方说，给你
```
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
```
：
- 如果问题 0 被解决了，那么你可以获得 3 分，但你不能解决问题 1 和 2 。
- 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的最高分数。

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5
解释：解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：7
解释：解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分
总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

提示：

1 <= questions.length <= 105
questions[i].length == 2
1 <= pointsi, brainpoweri <= 105

Code

240228

反向DP，从后往前，这样才无后效性。

class Solution {
public:
    long long getMax(long long a,long long b){
        return (a>b)?a:b;
    }
    long long mostPoints(vector<vector<int>>& questions) {
        int n=questions.size();
        vector<long long> dp(n);
        dp[n-1]=questions[n-1][0];
        for(int i=n-2;i>=0;i--){
            if(i+questions[i][1]+1<n)
                dp[i]=getMax(questions[i][0]+dp[i+questions[i][1]+1],dp[i+1]);
            else
                dp[i]=getMax(dp[i+1],questions[i][0]);
        }
        return dp[0];
    }
};

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

Code

240228

又是反向DP，无后效性。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(),coins.end());
        // int n=coins.size();
        vector<int> dp(amount+1,0x3f3f3f3f);
        dp[amount]=0;
        for(int i=amount-1;i>=0;i--){
            for(int coin:coins){
                if(INT_MAX-i<=coin) continue;
                if(coin+i<=amount)
                    dp[i]=min(dp[i],dp[i+coin]+1);
            }
        }
        return dp[0]==0x3f3f3f3f?-1:dp[0];
    }
};

Code2-WA

240324

现在又不会做了，真的牛皮。不过看了之前的解析我现在又会了。但是我还是把我的错误的正向dp代码再贴一遍。写得好丑。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(),coins.end(),greater<int>());
        int n=coins.size();
        int m=amount+1;
        vector<vector<int>> dp(n,vector<int>(m,-1));
        // for(int i=0;i<n;i++) dp[i][0]=0;
        dp[0][0]=0;
        for(int i=0;i<n;i++){
            if(i==0){
                for(int j=0;j<m;j++){
                    // if(j<coins[i]) dp[i][j]=0;
                    if(j>=coins[i] && dp[i][j-coins[i]]!=-1) dp[i][j]=dp[i][j-coins[i]]+1;
                }
            }else for(int j=0;j<m;j++){
                if(j<coins[i]){
                    dp[i][j]=dp[i-1][j];
                }else if(dp[i-1][j-coins[i]]==-1 && dp[i][j-coins[i]]==-1){
                    dp[i][j]=-1;
                }else if(dp[i-1][j-coins[i]]==-1){
                    dp[i][j]=dp[i][j-coins[i]]+1;
                }else if(dp[i][j-coins[i]]==-1){
                    dp[i][j]=dp[i-1][j-coins[i]]+1;
                }else



                dp[i][j]=min(dp[i-1][j-coins[i]],dp[i][j-coins[i]])+1;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cout<<dp[i][j]<<",";
            }
            cout<<"\n";
        }
        return dp[n-1][m-1];
    }
};

Code-Python

240324

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort()
        dp = [float('inf')] * (amount + 1)
        dp [amount] = 0
        for i in range(amount-1, -1, -1):
            for coin in coins:
                if coin + i <= amount:
                    dp[i]=min(dp[i],dp[coin + i]+1)
        # for i in range(amount-1, -1, -1):
        #     print(dp[i],end=",")
        return dp[0] if dp[0] != float('inf') else -1

2466. 统计构造好字符串的方案数

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

将 '0' 在字符串末尾添加 zero 次。
将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个长度在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为好字符串。

请你返回满足以上要求的不同好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余后返回。

示例 1：

输入：low = 3, high = 3, zero = 1, one = 1
输出：8
解释：
一个可能的好字符串是 "011" 。
可以这样构造得到："" -> "0" -> "01" -> "011" 。
从 "000" 到 "111" 之间所有的二进制字符串都是好字符串。

示例 2：

输入：low = 2, high = 3, zero = 1, one = 2
输出：5
解释：好字符串为 "00" ，"11" ，"000" ，"110" 和 "011" 。

提示：

1 <= low <= high <= 105
1 <= zero, one <= low

Code

240228

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high+1,0);
        dp[0]=1;
        for(int i=0;i<=high;i++){
            if(i+zero<=high) dp[i+zero]=(dp[i]+dp[i+zero])%1000000007;
            if(i+one<=high) dp[i+one]=(dp[i]+dp[i+one])%1000000007;
        }
        int sum=0;
        for(int i=low;i<=high;i++){
            sum=(sum+dp[i])%1000000007;
        }
        return sum;
    }
};

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了编码：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

Code

240228

样例太强了好几次没过。感觉这题考的是思维。

附上一部分样例：

"12"
"226"
"06"
"10"
"27"
"10011"
"230"

class Solution {
public:
    int numDecodings(string s) {
        if(s[0]=='0') return 0;
        int n=s.length();
        vector<int> dp(n+1,0);
        dp[0]=1,dp[1]=1;
        for(int i=2;i<=n;i++){
            if(s[i-1]=='0' && s[i-2]=='0') return 0;
            if(s[i-1]=='0' && s[i-2]>='3') return 0;
            if(s[i-1]=='0') dp[i]=dp[i-2];
            else if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]<='6')) dp[i]=dp[i-1]+dp[i-2];
            else dp[i]=dp[i-1];
        }
        for(int d:dp) cout<<d<<" ";
        cout<<endl;
        return dp[n];
    }
};

983. 最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

提示：

1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

Code1

240229

答案错误

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        // for(int day:days) cout<<day<<" ";
        // cout<<endl;

        // for(int i=0;i<3;i++) cout<<costs[i]<<" ";
        // cout<<endl;

        int n=days.size();
        vector<int> dp(n,0x3f3f3f3f);
        dp.back()=costs[0];
        int dur[3]={1,7,30};

        // for(int i=0;i<3;i++) cout<<dur[i]<<" ";
        // cout<<endl;

        for(int i=n-2;i>=0;i--){
            if(i!=n-1){
                dp[i]=min(dp[i+1]+costs[0],dp[i]);
            // for(int d:dp){
            //     cout<<d<<" ";
            // }
            // cout<<endl;
            }
            for(int j=1;j<3;j++){
                auto it=upper_bound(days.begin(),days.end(),days[i]-dur[j]+1);
                int len=it-days.begin();
                auto it_dp=dp.begin()+len;
                // if(it==days.end()) continue;
                *it_dp=min(dp[i+1]+costs[j],*it_dp);

            // for(int d:dp){
            //     cout<<d<<" ";
            // }
            // cout<<endl;
            }
            // cout<<endl;
        }
        return dp[0];
    }
};

Code2

240229

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        // cout<<"1,4,6,7,8,20"<<endl;
        int n=days.size();
        vector<int> dp(n,0);
        int dur[]={1,7,30};
        for(int i=n-1;i>=0;i--){
            vector<int>::iterator it[3];
            int back[3]={0,0,0};
            // cout<<"i="<<i<<", ";
            // auto it1=upper_bound(days.begin(),days.end(),days[i]+dur[0])
            for(int j=0;j<3;j++){
                it[j]=lower_bound(days.begin(),days.end(),days[i]+dur[j]);
                int len=it[j]-days.begin();
                auto it_dp=dp.begin()+len;
                // cout<<it[j]-days.begin()<<",";
                if(it[j]!=days.end()) back[j]=*it_dp+costs[j];
                else back[j]=costs[j];
                // cout<<back[j]<<" ";
            }
            // cout<<endl;
            dp[i]=min({back[0],back[1],back[2]});
        }
        // for(int d:dp){
        //     cout<<d<<" ";
        // }cout<<endl;
        return dp[0];
    }
};

790. 多米诺和托米诺平铺

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例 1:

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1
输出: 1

提示：

1 <= n <= 1000

Code

240301

class Solution {
public:
    int numTilings(int n) {
        vector<vector<int>> dp(n+1,vector<int>(4,0));
        dp[1]=vector<int>{1,0,0,1};
        for(int i=2;i<=n;i++){
            dp[i][0]=dp[i-1][3];
            dp[i][1]=(dp[i-1][2]+dp[i-1][0])%1000000007;
            dp[i][2]=(dp[i-1][0]+dp[i-1][1])%1000000007;
            dp[i][3]=((dp[i-1][1]+dp[i-1][2])%1000000007+(dp[i-1][3]+dp[i-1][0])%1000000007)%1000000007;
        }
        return dp[n][3];
    }
};

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

Code

240304

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2,0));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<n;i++){
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
            dp[i][0]=max(dp[i-1][1]-prices[i],dp[i-1][0]);
        }
        return max(dp[n-1][0],dp[n-1][1]);
    }
};

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

Code

240304

class Solution {
public:
    int n;
    void dfs(vector<vector<string>>& res,vector<string>& ans,string s,int i){
        if(i==n){
            res.emplace_back(ans);
            return;
        }
        for(int j=i;j<n;j++){
            int begin=i,end=j;
            while(begin<end){
                if(s[begin]!=s[end]) break;
                begin++;
                end--;
            }
            if(begin<end) continue;
            ans.emplace_back(s.substr(i,j-i+1));
            dfs(res,ans,s,j+1);
            ans.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        n=s.length();
        vector<vector<string>> vvs;
        vector<string> ans;
        dfs(vvs,ans,s,0);
        return vvs;
    }
};

97. 交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

Code

240304

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1=s1.length(),len2=s2.length(),len3=s3.length();
        if(len1+len2!=len3) return false;
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        dp[0][0]=1;
        for(int i=1;i<=min(len1,len3);i++){
            if(dp[i-1][0] && s1[i-1]==s3[i-1]) dp[i][0]=1;
            else break;
            // if(i==len3 && dp[i][0]) return true;
        }
        for(int j=1;j<=min(len2,len3);j++){
            if(dp[0][j-1] && s2[j-1]==s3[j-1]) dp[0][j]=1;
            else break;
            // if(j==len3 && dp[0][j]) return true;
        }
        cout<<"     ";
        for(int j=0;j<=len2;j++) cout<<j<<" ";
        cout<<endl;
        cout<<"i=0, ";
        for(int j=0;j<=len2;j++) cout<<dp[0][j]<<" ";
        cout<<endl;
        for(int i=1;i<=len1;i++){
            cout<<"i="<<i<<", "<<dp[i][0]<<" ";
            for(int j=1;j<=len2;j++){
                if(i+j>len3) break;
                if(s1[i-1]==s3[i+j-1] && dp[i-1][j]) dp[i][j]=1;
                if(s2[j-1]==s3[i+j-1] && dp[i][j-1]) dp[i][j]=1;
                cout<<dp[i][j]<<" ";
                if(i+j==len3 && dp[i][j]) return true;
            }
            cout<<endl;
        }
        // if(len3==0) return true;
        // for(int i=1;i<=len1;i++){
        //     if(len3-i<=len2 && len3-i>=1 && dp[i][len3-i]) return true;
        // }
        if(dp[len1][len2]) return true;
        return false;
    }
};

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都保证是一个 32-位 整数

Code

240304

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>> dp(n+1,vector<int>(2));
        dp[0][0]=1;//最大正数
        dp[0][1]=1;//最大负数
        int MAX=-11;
        for(int i=1;i<=n;i++){
            dp[i][0]=max({dp[i-1][0]*nums[i-1],dp[i-1][1]*nums[i-1],nums[i-1]});
            dp[i][1]=min({dp[i-1][0]*nums[i-1],dp[i-1][1]*nums[i-1],nums[i-1]});
            MAX=max(MAX,dp[i][0]);
            cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
        }
        return MAX;
    }
};

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Code

240304

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

264. 丑数 II

给你一个整数 n ，请你找出并返回第 n 个丑数。

丑数就是质因子只包含 2、3 和 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

1 <= n <= 1690

Code1

240307

因为对于样例：10，会输出这样的数组：[1,2,3,4,5,6,6,8,9,10]。所以我加了一个判断if(dp[i]==dp[i-1]) i--;。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n);
        dp[0]=1;
        int cur_2=0,cur_3=0,cur_5=0;
        for(int i=1;i<n;i++){
            dp[i]=min({dp[cur_2]*2,dp[cur_3]*3,dp[cur_5]*5});
            if(dp[i]==dp[cur_2]*2) cur_2++;
            else if(dp[i]==dp[cur_3]*3) cur_3++;
            else cur_5++;
            if(dp[i]==dp[i-1]) i--;
        }
        // for(int i=0;i<n;i++) cout<<dp[i]<<" ";
        return dp[n-1];
    }
};

Code2

240307

但是这样子就不需要判断了。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n);
        dp[0]=1;
        int cur_2=0,cur_3=0,cur_5=0;
        for(int i=1;i<n;i++){
            dp[i]=min({dp[cur_2]*2,dp[cur_3]*3,dp[cur_5]*5});
            if(dp[i]==dp[cur_2]*2) cur_2++;
            if(dp[i]==dp[cur_3]*3) cur_3++;
            if(dp[i]==dp[cur_5]*5) cur_5++;
        }
        return dp[n-1];
    }
};

313. 超级丑数

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32 
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。

提示：

1 <= n <= 105
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列

Code

240307

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> dp(n);
        dp[0]=1;
        int m=primes.size();
        vector<int> cur(m,0);
        for(int i=1;i<n;i++){
            long long Min=INT_MAX;
            for(int i=0;i<m;i++){
                Min=min(Min,(long long)primes[i]*dp[cur[i]]);
            }
            for(int i=0;i<m;i++){
                if(Min==(long long)primes[i]*dp[cur[i]]) cur[i]++;
            }
            dp[i]=Min;
            // if(dp[i]==dp[i-1]) i--; //超时
        }
        // for(int i=0;i<n;i++) cout<<dp[i]<<","; //太占oi了
        return dp[n-1];
    }
};

718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

Code

240307

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n=nums1.size(),m=nums2.size(),Max=0;
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    Max=max(Max,dp[i][j]);
                }
                // else{
                //     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                // }
            }
        }
        // cout<<"  ";
        // for(int i=0;i<n;i++) cout<<nums2[i]<<" ";
        // cout<<endl;
        // for(int i=1;i<=n;i++){
        //     cout<<nums1[i-1]<<" ";
        //     for(int j=1;j<=m;j++){
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        return Max;
    }
};

343. 整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

2 <= n <= 58

Code

240307

class Solution {
public:
    int integerBreak(int n) {
        vector<long long> dp(n+1);
        dp[1]=1,dp[2]=1;
        for(long long i=3;i<=n;i++){
            for(long long j=1;j<=i/2;j++){
                long long front=max(j,dp[j]);
                long long back=max(i-j,dp[i-j]);
                dp[i]=max(dp[i],front*back);
            }
        }
        // for(int i=1;i<=n;i++) cout<<dp[i]<<",";
        return dp[n];
    }
};

935. 骑士拨号器

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。

象棋骑士可能的移动方式如下图所示:

我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。

给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。

你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。

因为答案可能很大，所以输出答案模 109 + 7.

示例 1：

输入：n = 1
输出：10
解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。

示例 2：

输入：n = 2
输出：20
解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

示例 3：

输入：n = 3131
输出：136006598
解释：注意取模

提示：

1 <= n <= 5000

Code

240307

class Solution {
public:
    int knightDialer(int n) {
        const int MOD=1000000007;
        vector<vector<int>> v{{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{0,1,7},{2,6},{1,3},{2,4}};
        vector<vector<int>> dp(1,vector<int>(10,1));
        dp.resize(n,vector<int>(10,0));
        for(int i=1;i<n;i++){
            for(int j=0;j<10;j++){
                for(int k:v[j]){
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
                }
            }
        }
        int sum=0;
        for(int k:dp[n-1]){
            sum=(sum+k)%MOD;
        }
        return sum;
    }
};

978. 最长湍流子数组

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。

如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：

若
```
i <= k < j
```
：
- 当 k 为奇数时， A[k] > A[k+1]，且
- 当 k 为偶数时，A[k] < A[k+1]；
或

若
```
i <= k < j
```
：
- 当 k 为偶数时，A[k] > A[k+1] ，且
- 当 k 为奇数时， A[k] < A[k+1]。

示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

示例 2：

输入：arr = [4,8,12,16]
输出：2

示例 3：

输入：arr = [100]
输出：1

提示：

1 <= arr.length <= 4 * 104
0 <= arr[i] <= 109

Code

240307

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n=arr.size();
        vector<vector<int>> dp(n,vector<int>(2,1));
        // dp[0][0]=1;//不包含本元素
        // dp[0][1]=1;//包含本元素
        if(n>=2){
            // dp[1][0]=max(dp[0][1],dp[0][0]);
            if(arr[1]!=arr[0]) dp[1][1]=2;
        }
        for(int i=2;i<n;i++){
            if((arr[i-1]>arr[i-2] && arr[i-1]>arr[i])||
               (arr[i-1]<arr[i-2] && arr[i-1]<arr[i])){
                dp[i][1]=dp[i-1][1]+1;
            }else if(arr[i-1]!=arr[i]) dp[i][1]=2;
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        }
        // for(int i=0;i<n;i++) cout<<dp[i][0]<<",";
        // cout<<endl;
        // for(int i=0;i<n;i++) cout<<dp[i][1]<<",";
        // cout<<endl;
        return max(dp[n-1][0],dp[n-1][1]);
    }
};

DP专题

https://acm.nanyan.cc/posts/4366.html

作者

nanyan

发布于

2024年1月28日

许可协议

ACWing Prime Algorithm 上一篇

202401卓裂学院转专业-上机测试下一篇