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

article/2024/4/13 14:33:56

链接 : 

. - 力扣(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] ;}
};

最后 : 

算法交流群 : 245742652


http://www.ngui.cc/article/show-1927657.html

相关文章

使用Docker -compose启动自定义jar包

步骤1&#xff1a;编写docker-compose.yml文件 首先我们需要编写一个docker-compose.yml文件来定义我们的服务传到我们的云服务器上 以下是一个示例&#xff1a; version: 3 services:app:build:context: .dockerfile: Dockerfileports:- 8080:8080volumes:- ./app.jar:/app…

【Mars3d】进行水平测量measure.area({的时候,会被模型遮挡的处理方法

问题&#xff1a; 1.thing/analysis/measure 水平面积 measure.area({ 在模型上测量的时候会被遮挡 2. 通过 addHeight:10000,增加高度也不可以实现这种被遮挡的效果&#xff0c;都增加到10000了&#xff0c;还是会被遮挡 export function measureArea() { measure.area({ s…

将所有字母转化为该字母后的第三个字母,即A->D,B->E

//编写加密程序&#xff0c;规则&#xff1a;将所有字母转化为该字母后的第三个字母&#xff0c;即A->D,B->E,C->F,…Y->B,Z->C //小写字母同上&#xff0c;其他字符不做转化。输入&#xff1a;I love 007 输出&#xff1a;L oryh 007 代码&#xff1a; #inc…

小程序原生 API

微信原生 API 1. API 基础 小程序开发框架提供丰富的微信原生 API&#xff0c;可以方便的调起微信提供的能力&#xff0c;如获取用户信息&#xff0c;本地存储&#xff0c;支付功能等&#xff0c;几乎所有小程序的 API 都挂载在 wx 对象底下&#xff0c;例如&#xff1a;wx.c…

钉钉机器人发送折线图卡片 工具类代码

钉钉机器人 “创建并投放卡片 接口 ” 可以 发送折线图、柱状图 官方文档&#xff1a;创建并投放卡片 - 钉钉开放平台 0依赖、1模板、2机器人放到内部应用、3放开这个权限 、4工具类、5调用工具类 拼接入参 卡片模板 自己看文档创建&#xff0c;卡片模板的id 有用 0、依赖…

Facebook的元宇宙实践:数字化社交的新前景

近年来&#xff0c;元宇宙&#xff08;Metaverse&#xff09;这一概念备受瞩目&#xff0c;被认为是数字化社交的未来趋势之一。而在众多科技巨头中&#xff0c;Facebook&#xff08;现更名为Meta&#xff09;一直处于元宇宙发展的前沿。在本文中&#xff0c;我们将深入探讨Fac…

flask 数据库迁移报错 Error: No such command ‘db‘.

初学FLASK&#xff0c;使用pycharm的terminal 启动&#xff0c;实现数据库迁移 文件结构 项目启动文件不在一级目录pycharm>terminal启动 由于自己初入 python flask 很多东西并不懂&#xff0c;只能依葫芦画瓢&#xff0c;使用如下命令,输入完第一行命令执行没有任何错误…

react Hook useEffect的基本使用及注解

一、概述 useEffect是React提供的一个Hook&#xff0c;用于在函数组件中执行副作用操作。副作用操作通常包括数据获取、订阅事件、手动操作DOM等。useEffect可以让我们在函数组件中模拟类组件的生命周期方法&#xff08;如componentDidMount、componentDidUpdate、componentWi…

vue自定义实现icon选择器

<template> <div> <span class"iconStyle" click"selectIcon"> <i :class"value" /> </span> <div class"iconTitle">选择图标</div> <el-dialog title"" :visible.sync"…

Unity中URP实现水体(整理优化)

文章目录 前言一、优化水的深度1、我们把 水流动的方向 和 水深浅过渡值&#xff0c;整合到一个四维变量中2、修改 水体流动方向3、在片元着色器中&#xff0c;修改使用过渡变量 二、优化泡沫三、优化水下的扭曲1、修复原本扰动UV的计算 四、优化水面高光1、把高光强度、光滑度…