当前位置: 首页 > article >正文

力扣每日一题 单调数组对的数目(dp)

 题目

困难  动态规划

给你一个长度为 n 的  整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件,我们称它们是 单调 数组对:

  • 两个数组的长度都是 n 。
  • arr1 是单调 非递减 的,换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
  • arr2 是单调 非递增 的,换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
  • 对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有 单调 数组对的数目。

由于答案可能很大,请你将它对 109 + 7 取余 后返回。

示例 1:

输入:nums = [2,3,2]

输出:4

解释:

单调数组对包括:

  1. ([0, 1, 1], [2, 2, 1])
  2. ([0, 1, 2], [2, 2, 0])
  3. ([0, 2, 2], [2, 1, 0])
  4. ([1, 2, 2], [1, 1, 0])

示例 2:

输入:nums = [5,5,5,5]

输出:126

提示:

  • 1 <= n == nums.length <= 2000
  • 1 <= nums[i] <= 50

 思路

 题目要求求出符合条件的数组数量,刚开始想着用搜索来做的,想了一下复杂度太高了,就考虑动态规划
 

根据题目中 arr1[i] + arr2[i] = nums[i],我们可以知道一旦确定了arr1的取值,arr2也会随之确定,其中 arr2[i]= nums[i]-arr1[i],所以我们直接枚举arr1的情况,通过条件筛选对应的arr2即可

开一个二维数组dp,其中dp[i][j]代表arr1数组第i个数取j时符合条件的数组对的数量

要求第i个数取j时符合条件的数组对的数量就要看第i-1个数取符合条件的数时数组对的数量

要求第i-1个数取j时符合条件的数组对的数量就要看第i-2个数取符合条件的数时数组对的数量

..........................................................

这很动态规划,由子问题求解大问题

初始化

当i=0时,arr1[0]可以取值的范围为0-nums[0],所以先给dp数组的dp[0][0]~dp[0][nums[0]]赋值为1,方便后面迭代计算

当i>=1时,设v2为arr1[i]对应的数,v1为arr1[i-1]对应的数

每次先枚举v2,v2的取值范围为0-nums[i],然后由于arr1数组是非递减的,所以v1<=v2,v1的取值范围为0-v2,此时仅仅只是确定了arr1的条件

        for(int i=1;i<n;i++){
            //枚举当前位置的数
            for(int v2=0;v2<=nums[i];v2++){
                //枚举前一个数
                for(int v1=0;v1<=v2;v1++){


                }

            }
        }

还要考虑arr2,设v2t为arr2[i]对应的数,v1为arr2[i-1]对应的数

由于v1+v1t=nums[i-1],v2+v2t=nums[i]

可得v1t=nums[i]-v1,v2t=nums[i]-v2

由于arr2数组是非递增的,所以有v1t>=v2t

由以上推导我们利用两层循环筛选符合条件的v1和v2

同时利用题目中arr1[i] + arr2[i] = nums[i]的性质得到arr2对应的v1t和v2t判断条件,符合条件的话就将对应的dp[i-1][v1]累加到dp[i][v2]中

下面上代码

class Solution {
    public int countOfPairs(int[] nums) {
        int n=nums.length;
        int mod=1000000007;
        int[][] dp=new int[n][55];
        //第一个数字可以取0~nums[0],dp数组全部置为1
        for(int i=0;i<=nums[0];i++){
            dp[0][i]=1;
        }

        for(int i=1;i<n;i++){
            //枚举当前位置的数
            for(int v2=0;v2<=nums[i];v2++){
                //枚举前一个数
                for(int v1=0;v1<=v2;v1++){
                    //arr2[i-1]
                    int v1t=nums[i-1]-v1;
                    //arr2[i]
                    int v2t=nums[i]-v2;
                    //arr2[i-1]>=arr2[i]时才符合条件
                    if(v1t>=v2t){

                        dp[i][v2]=(dp[i][v2]+dp[i-1][v1])%mod;
                    }

                }

            }
        }
        int ans=0;
        //累加取答案
        for(int i=0;i<=nums[n-1];i++){
            ans=(ans+dp[n-1][i])%mod;
        }

        return ans;
    }
}


http://www.kler.cn/a/415285.html

相关文章:

  • Android studio 签名加固后的apk文件
  • 配置泛微e9后端开发环境
  • GaussDB高智能--智能优化器介绍
  • SQL Server数据库日志(ldf文件)清理
  • web安全之信息收集
  • AD7606使用方法
  • 期权懂|期权中的期权到期日引力是什么意思?
  • TextFSM模板太复杂?ntc-templates让一切变得简单!
  • Android studio与JS交互
  • Android Studio 右侧Gradle窗口只有test的task问题解决
  • pytest+allure生成报告显示loading和404
  • 浅谈C#库之DevExpress
  • Rust 组织管理
  • 知识点回顾
  • python的文件操作练习
  • 基于Java Springboot社区助老志愿者服务平台
  • 如何在 GitHub 上下载并切换到仓库的历史版本
  • Java学习,反射
  • 常用指标采集 exporter
  • 前端网络安全分析
  • 知识蒸馏中有哪些经验| 目标检测 |mobile-yolov5-pruning-distillation项目中剪枝知识分析
  • 在内网工作时,如何使用 vscode remote ssh 去连接内网服务器?
  • 开源项目:纯Python构建的中后台管理系统
  • 解决 YOLOv5 加载模型时 ‘AttributeError Can‘t get attribute ‘SPPF‘‘ 错误的方法
  • 【sqlcipher】pc端sqflite使用过程中遇到的问题
  • 一个5位数,判断它是不是回文数。即12321是回文数,个位与万位相同,十位与千位相同。-多语言