lc 每日一题 2024 - 03 - 01 划分型dp

链接 :

. - 力扣（LeetCode）

思路 :

子集划分型dp , 设置dp[i+1]表示前i个数字能否有效划分；

那么一个划分好的数组 + 两个相等的数字，新形成的数组也是有效划分数组;

同理，加上三个相等或三个递增的数字，新形成的数组也是有效划分数组 ;

先写出判断表达式 :

    bool pd2(int x,int y){//判断新加的2个是否有效
        return x == y ;
    }

    bool pd3(int a,int b,int c){// 判断新加的3个是否有效
        return (a==b&&b==c) || (a+1==b &&b+1==c) ;
    }

然后写出状态转移方程式 :

dp[i] = (i>=2 &&pd2(a[i-2],a[i-1])) || (i>=3 && pd3(a[i-3],a[i-2],a[i1])) ;

然后写方程就好了 :

代码 :

class Solution {
public:

    bool pd2(int x,int y){//判断新加的2个是否有效
        return x == y ;
    }

    bool pd3(int a,int b,int c){// 判断新加的3个是否有效
        return (a==b&&b==c) || (a+1==b &&b+1==c) ;
    }

    bool validPartition(vector<int>& nums) {
        int n = nums.size() ;
        vector<bool> dp(n+1 , false) ;
        dp[0] = true ;// 已经划分好了 
        // dp[i + 1] 表示nums的前i个数是不是能够有效划分
        for(int i=1;i<=n;i++){
            if(i>=2){
                dp[i] = dp[i-2] && pd2(nums[i-2],nums[i-1]);
            }
            if(i>=3){
                dp[i] = dp[i] || dp[i-3] && pd3(nums[i-3],nums[i-2],nums[i-1]) ;
            }
        }
        return dp[n] ;
    }
};