算法系列--动态规划--特殊的状态表示--分析重复子问题

本文主要是介绍算法系列--动态规划--特殊的状态表示--分析重复子问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

💕"轻舟已过万重山!"💕
作者:Lvzi
文章主要内容:算法系列–算法系列–动态规划–特殊的状态表示–分析重复子问题
在这里插入图片描述

大家好,今天为大家带来的是算法系列--动态规划--特殊的状态表示--分析重复子问题

一.组合总数IV

链接:
https://leetcode.cn/problems/combination-sum-iv/
在这里插入图片描述
分析:

本题名字叫做组合问题,但实际上是一个排列问题,需要说明的是背包问题解决的是有限制条件下的"组合"问题,本题是一个排列问题,其实根本就无法使用背包问题的思路解决

那该如何解决呢?而且这道题还不太容易分析状态表示,其实这是动态规划问题中比较难的一种问题,状态表示的确立应该是:在分析问题的时候,发现重复的子问题,并抽象出状态表示

在这里插入图片描述
目的是求出总和等于target的所有排列方式,如果固定第一个数为a,那么就是求出总和等于target-a的所有排列方式,这里的重复子问题就是求出总和等于某个数的所有排列方式

状态表示:

  • dp[i]:总和等于i的所有排列方式

状态转移方程:
还是根据最后一个位置的状态划分问题
在这里插入图片描述
nums[j]表示的是数组中任意的一个数,只要符合条件(i >= nums[j]),都可以作为组成总和为i的排列方式的一种,那么只需在前面判断组成和为i-nums[j]的所有排列数即可,即dp[i - nums[j](注意本题是排列,排列!!!是区分顺序的!!!)

初始化:

  • dp[0] = 1:凑出总和为0的所有方式–>什么也不选–>空集也算一种情况

代码:

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for(int i = 1; i <= target; i++)for(int j = 0; j < nums.length; j++)if(i >= nums[j])dp[i] += dp[i - nums[j]];return dp[target];}
}

根据状态表示可以推导出最后应该返回的结果为总和为target的所有排列方式,但是这些排列方式的组合中必须包含数组中的数字

二.不同的二叉搜索树

链接:
https://leetcode.cn/problems/unique-binary-search-trees/
在这里插入图片描述
分析:

做之前一定要知道什么是二叉搜索树,二叉搜索树是指一课二叉树的所有子树都满足left < root < right

本题同样也可以采用在分析问题的时候,发现重复的子问题,并抽象出状态表示的分析方法
在这里插入图片描述
这里的重复子问题就是选择一个数作为根节点之后,统计其所有的情况,一直统计完所有的数

状态表示:

  • dp[i]:结点的个数为i时,一共有多少种二叉搜索树

状态转移方程:
在这里插入图片描述

初始化:

  • dp[0] = 1:空树也算是二叉搜索树

代码:

class Solution {public int numTrees(int n) {int[] dp = new int[n + 1];dp[0] = 1;// 初始化for(int i = 1; i <= n; i++)// 枚举节点的总数for(int j = 1; j <= i; j++)// 选择每一个根节点dp[i] += dp[j - 1] * dp[i - j];// 填表return dp[n];}
}

动态规划的系列就此完结!

这篇关于算法系列--动态规划--特殊的状态表示--分析重复子问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/862681

相关文章

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

基于Python实现一个PDF特殊字体提取工具

《基于Python实现一个PDF特殊字体提取工具》在PDF文档处理场景中,我们常常需要针对特定格式的文本内容进行提取分析,本文介绍的PDF特殊字体提取器是一款基于Python开发的桌面应用程序感兴趣的... 目录一、应用背景与功能概述二、技术架构与核心组件2.1 技术选型2.2 系统架构三、核心功能实现解析

Flutter监听当前页面可见与隐藏状态的代码详解

《Flutter监听当前页面可见与隐藏状态的代码详解》文章介绍了如何在Flutter中使用路由观察者来监听应用进入前台或后台状态以及页面的显示和隐藏,并通过代码示例讲解的非常详细,需要的朋友可以参考下... flutter 可以监听 app 进入前台还是后台状态,也可以监听当http://www.cppcn