灵神DP题单---划分型 DP---§6.1 判定能否划分

这里的状态定义一般使用DP【i】 表示 考虑前i个东西能否满足条件，然后我们枚举上一次的转移位置就好了

2369. 检查数组是否存在有效划分

需要注意的是我习惯从1开始写，所以要处理好边界的下标问题

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        vector<int>dp(n+10);


        dp[0] = 1;
        for(int i=2;i<=n;i++){
            if(i-2>=0&&nums[i-1]==nums[i-2])dp[i]|=dp[i-2];
            if(i-3>=0&&nums[i-1]==nums[i-2]&&nums[i-1]==nums[i-3])dp[i]|=dp[i-3];
            if(i-3>=0&&nums[i-1]==nums[i-2]+1&&nums[i-1]==nums[i-3]+2)dp[i]|=dp[i-3];
        }

        return dp[n];

    }
};

139. 单词拆分

和上面的思路相同，直接搞一下就好了，在字符串s上 划分DP一下

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        int m = wordDict.size();
        vector<int>dp(n+10);
        dp[0] = 1;

        for(int i=1;i<=n;i++){
            for(int j=0;j<m;++j){
                int sz = wordDict[j].size();
                if(i-sz<0)continue;
                string tem = s.substr(i-sz,sz);
                if(tem==wordDict[j])dp[i]|=dp[i-sz];
            }
        }

        for(int i=1;i<=n;i++)cout<<dp[i]<<" ";


        return dp[n];

    }
};