Studying-代码随想录训练营day34| 62.不同路径、63.不同路径II、343.整数拆分、96.不同的二叉搜索树

第34天,动态规划part02,牢记五部曲步骤,编程语言:C++

目录

62.不同路径

63.不同路径II

343.整数拆分 

96.不同的二叉搜索树 

总结


62.不同路径

文档讲解:代码随想录不同路径

视频讲解:手撕不同路径

题目:

学习:本题最直观的是使用图论的深度搜索的方法,来枚举出来有多少种路径,总时间复杂度为O(2^(m + n - 1) - 1),时间复杂度是非常大的,在力扣中是超时的。因此本题可以采取动态规划的方法来降低时间复杂度。

使用动态规划方法,可以从动态五部曲入手。

1.确定dp数组以及下标含义:本题类似于一个二维棋盘,因此我们可以设置一个二维dp数组,dp[i][j],就表示为到达i行j列位置的路径总数。

2.确定递推公式:依据题干我们知道到达i行j列,我们只能从i-1行j列,和i行j-1列到达。因此dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

3.dp数组的初始化:首先依据题干我们可以知道到达第一行各点的路径数量都为1, 也即一直往右走,到达第一列各点的路径数量同理也都为1,因此我们对第一行和第一列进行初始化。

4.确定遍历顺序,依据递推公式我们可以确定每个点都是从其上方和左方推导而来的,因此我们从左到右一层一层遍历即可。

5.距离推导dp数组:

代码:

//时间复杂度O(m*n)
//空间复杂度O(m*n)
class Solution {
public:int uniquePaths(int m, int n) {//1.确定dp数组和下标含义vector<vector<int>> dp(m, vector<int>(n, 0));//其中dp[i][j]表示到达i行j列共有多少条不同的路径//2.确定递推公式//由于每次只能向下或者向右,因此dp[i][j] = dp[i-1][j] + dp[i][j-1]//3.初始化dp数组,由递推公式可知,我们应该初始化所有i=0和j=0的位置,同时,根据题干我们也能知道这些位置都是1for(int i = 0; i < m; i++) {dp[i][0] = 1;}for(int j = 0; j < n; j++) {dp[0][j] = 1;}//4.确定遍历顺序,可知每个点都是从其上方和左方推导而来的,因此我们需要从上至下,从左至右进行遍历for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}//5.打印dp数组//cout << dp[i][j] << endl; //调试的时候使用}return dp[m - 1][n - 1];}
};

本题还可以通过数论来进行求解,由题意可知,我们无论如何都是要走m+n-2步才能到达终点的,其中由m-1步是要往下走的,不同路径就取决于这m-1步什么时候走,因此通过排列组合能够推出,总共的取法为Cm+n-2(上标m-1)。

代码:使用数论最关键的是防止两个int相乘出现溢出的情况,因此我们需要在计算分子的时候,不断除以分母。

//时间复杂度O(m)
//空间复杂度O(1)
class Solution {
public:int uniquePaths(int m, int n) {long long numerator = 1; // 分子int denominator = m - 1; // 分母int count = m - 1;int t = m + n - 2;while (count--) {numerator *= (t--);while (denominator != 0 && numerator % denominator == 0) {numerator /= denominator;denominator--;}}return numerator;}
};

63.不同路径II

文档讲解:代码随想录不同路径II

视频讲解:手撕不同路径

题目:

学习:本题与上一题不同在于存在障碍物,因此我们需要对障碍物进行单独处理。从动态五部曲出发:

1.确定dp数组:与上一题一样,设置二维dp数组,dp[i][j]表示从起始点出发,到达(i,j)的不同路径数量。

2.确定递推公式:递推公式与上一题一样,但是要注意障碍物单独处理,也即有障碍物的地方就不用再进行赋值了(初始为0)

if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候,再推导dp[i][j]dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}

3.dp数组初始化:同样也是第一行,第一列为1,但是要注意如果第一行出现障碍物,或者第一列出现障碍物,后面的格子就到达不了了,就不进行1的赋值了。(因为只能往下和右走,不能绕路)

4.确定遍历顺序,遍历顺序与上一题相同。

代码:

//时间复杂度O(n*m)
//空间复杂度O(m)
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {//剪枝处理,如果起始点有障碍物或者,终点有障碍物,则不能到达终点int m = obstacleGrid.size(); //行int n = obstacleGrid[0].size(); //列if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;//1.确定dp数组及下标含义//dp[i][j]就表示到达i行j列有的路径数量vector<vector<int>> dp(m,vector<int>(n, 0));//2.确定递推公式//dp[i][j] = dp[i - 1][j] + dp[i][j - 1],但是要注意如果obstacleGrid[i][j]处有障碍物,则不进行赋值//3.初始化dp数组,也是需要赋值第一行和第一列,不同的在于如果第一行或者第一列上有障碍物,则后面的都无法到达,为0for(int i = 0; i < m; i++) {if(obstacleGrid[i][0] == 1) break; //遇到障碍物,后面的都无法抵达,保持为0dp[i][0] = 1;}for(int j = 0; j < n; j++) {if(obstacleGrid[0][j] == 1) break;dp[0][j] = 1;}//4.确定遍历顺序,从上至下,从左至右for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {if(obstacleGrid[i][j] == 0) { //不是障碍物时再进行赋值dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}
};

343.整数拆分 

文档讲解:代码随想录整数拆分

视频讲解:手撕整数拆分

题目:

学习:本题难点在于找到递推公式,也即找到数与数之间的关系。以动规五部曲来说。

1.确定dp数组以及下标的含义,依据题意我们可以设置一个一维的dp数组,dp[i]就表示为n = i时,乘积的最大值。

2.确定递推公式:我们需要思考dp[i]的最大值该如何得到,对于比i小的数来说,例如dp[i - 1],dp[i - 2],它们分别表示了对i - 1拆分后乘积能够得到的最大值,以及对i - 2拆分后乘积能够得到的最大值,相较于i,它们之间就差一个差值,也即dp[i] 有可能会是 1*dp[i -1]也有可能会是2*dp[i-2]以此类推,这是获得dp[i]的一个途径。其次我们知道1*dp[i-1]中的dp[i-1]是对i-1进行整数拆分后得到的最大乘积,因此我们还错过了1*(i-1)的可能,虽然一般来说1*dp[i-1]是大于1*(i-1)的,但不保证中间不会有更大的情况出现。综上我们可以得出递推公式为:dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

3.dp数组的初始化:要注意对于0和1来说,实际上是拆分不了的,因为题干要求了,至少拆分为2个数,且n>=2,因此我们这里对dp[2]进行初始化,dp[2]=1;

4.确定遍历顺序:显然我们需要依靠dp[i - j]的状态,所以i一定要从前往后遍历。

5.举例推导dp数组:

代码:

class Solution {
public:int integerBreak(int n) {//1.确定dp数组以及下标的含义vector<int> dp(n + 1); //dp[i]表示n=i时的最大乘积//2.确定递推公式:dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j) 对j进行遍历//3.初始化dp数组:dp[0]和dp[1]都没有意义dp[2] = 1;//4.确定遍历顺序,外层需要对i进行从小到达遍历进行赋值,内层对j进行遍历,找到最大值for(int i = 3; i < n + 1; i++) {for(int j = 1; j <= i - 2; j++) { //最多取到i - dp[i] = max(dp[i], max(j*(i - j), j*dp[i - j]));//max只能同时比较两个数} }return dp[n];}
};

代码:可以对j的范围进行优化,根据数论,对一个数进行拆分,尽可能拆成相同的数最后得到会是最大的,因为a+b >= 2根号(ab),因此要ab最大,就是取等于号的时候,此时a = b。

//时间复杂度O(n^2)
//空间复杂度O(n)
class Solution {
public:int integerBreak(int n) {//1.确定dp数组以及下标的含义vector<int> dp(n + 1); //dp[i]表示n=i时的最大乘积//2.确定递推公式:dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j) 对j进行遍历//3.初始化dp数组:dp[0]和dp[1]都没有意义dp[2] = 1;//4.确定遍历顺序,外层需要对i进行从小到达遍历进行赋值,内层对j进行遍历,找到最大值for(int i = 3; i < n + 1; i++) {for(int j = 1; j <= i/2; j++) { //最多取到i - dp[i] = max(dp[i], max(j*(i - j), j*dp[i - j]));//max只能同时比较两个数} }return dp[n];}
};

96.不同的二叉搜索树 

文档讲解:代码随想录不同的二叉搜索树

视频讲解:手撕不同的二叉搜索树

题目:

学习:本题同样找到递推公式是关键,依据动规五部曲我们进行分析。

1.确定dp数组以及下标含义:在这里我们需要找到给定节点个数,能够得到的二叉搜索树种数。因此我们可以创建一个一维dp数组,dp[i]就表示i个节点能够得到的二叉搜索树种数。

2.确定递推公式:我们从n=1和n=2来看,对于n=1来说显然只有一棵二叉搜索树,n=2则有两棵二叉搜索树。

n=3时,则有5棵二叉搜索树

分析n=3的情况,当1为头节点时,实际上左子树节点数为0,右子树节点数为2,因此右子树共有n=2种可能。当2为头节点时,左子树节点数为1,右子树节点数为1,因此左右子树都是n=1种可能,乘起来就是1种可能。当3为头节点,左子树节点数为2,右子树节点数为0,因此左子树共有n=2种可能,右子树只有1种可能,乘起来就是2种可能。以此我们可以得出一个公式:dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]。由此我们可以推出:dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]。

所以递推公式:dp[i] += dp[j - 1] * dp[i - j]; ,j-1 为j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量。

3.dp数组初始化:空节点实际上也可以作为一棵树包括空节点,左子树为空,右子树为空的情况,因此需要进行初始化dp[0] = 1,对于1个节点也能够通过dp[0]推出。

4.确定遍历顺序:从递归公式:dp[i] += dp[j - 1] * dp[i - j]可以看出,节点数为i的状态是依靠 i之前节点数的状态。

5.举例推导dp数组:

代码:

//时间复杂度O(n^2)
//空间复杂度O(n)
class Solution {
public:int numTrees(int n) {//1.确定dp数组以及下标含义vector<int> dp(n + 1); //dp[i] 表示i个节点能够组成的二叉搜索树的种类//2.确定递推公式:dp[i] += dp[j - 1] * dp[i - j] //对j进行遍历//3.初始化dp数组:由于空节点实际上也是一颗二叉树,,因此需要初始化dp[0] = 1;//dp[1] = 1; //可以进行初始化,也可以通过dp[0]推导而来//4.确定遍历顺序,从小到大进行遍历for(int i = 1; i < n + 1; i++) {for(int j = 1; j <= i; j++) {dp[i] += dp[j - 1]*dp[i - j];}}return dp[n];}
};

总结

做动态规划一定要牢记,动规五部曲。推导递推公式时,最重要的是从简单的往复杂的推,逐一分析找到关系。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3223731.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

接口测试(3)

接口自动化 # 获取图片验证码import requestsresponse requests.get(url"http://kdtx-test.itheima.net/api/captchaImage")print(response.status_code) print(response.text) import requestsurl "http://kdtx-test.itheima.net/api/login" header_da…

爱情和友情触动人心

在这个纷繁复杂的娱乐圈里&#xff0c;爱情与友情的故事总是能触动人心&#xff0c;而“于适前女友包场于适新电影”的新闻&#xff0c;无疑为这个充满故事的舞台又添上了一抹温暖的色彩。这不仅仅是一场电影的包场&#xff0c;更是一段超越常规情感的展现&#xff0c;不禁感叹…

网络安全——防御实验

防御实验一 拓扑结构展示&#xff1a; 一、 根据题目&#xff0c;先为办公区做安全策略主要策略有以下几点&#xff1a; 1、书写名称和描述&#xff0c;名称和描述要明确&#xff0c;让除本人以外的人也能理解 2、确定源地址为办公区&#xff0c;目标地址为DMZ区 3、确定时间…

Xilinx zc706 USB电路解析

作者 QQ群&#xff1a;852283276 微信&#xff1a;arm80x86 微信公众号&#xff1a;青儿创客基地 B站&#xff1a;主页 https://space.bilibili.com/208826118 参考 USB OTG检测原理 USB3320 USB_ID为低电平时候&#xff0c;为host模式&#xff0c;USB_ID为悬空&#xff08;高…

锅总反驳李彦宏说的“不要卷模型,要卷应用”

李彦宏的观点是大家不要卷模型&#xff0c;要卷应用&#xff0c;但我认为这种看法是荒谬的。以下是24条反驳李彦宏观点的论点和论据&#xff1a; 模型的准确性直接决定应用的质量和用户体验&#xff1a; 论据&#xff1a;在自然语言处理、计算机视觉等领域&#xff0c;模型的准…

哦华为仓颉语言

本来我不太想说的&#xff0c;奈何有不少粉丝提问提到了这语言&#xff0c;目前的情况我不透露太多&#xff0c;看过这课程C实现一门计算机编程语言到手撸虚拟机实战的懂的自然懂。 在互联网领域几乎大部分应用软件运行在X86 LINUX上居多&#xff0c;如果你有问题可以先学习这…

C++入门基础(2)

目录 一、引用: 1、定义&#xff1a; 2、特性&#xff1a; 3、引用的使用&#xff1a; 4、const引用&#xff1a;控制权限 const引用定义: const引用可以接收3种对象&#xff1a; 1、正常对象&#xff1a; 2、临时对象&#xff1a; 3、const对象&#xff1a; 总结&…

怎么转播别人的直播

转播别人的直播&#xff0c;特别是实现无缝的实时转播&#xff0c;可以通过一些平台的功能来实现&#xff0c;比如快手和抖音。下面是一个基本的步骤说明&#xff0c;但请注意&#xff0c;具体操作可能会因平台更新或政策变化而有所不同&#xff1a; 找到想要转播的直播间&…

新品茶叶如何一炮而红?营销高手的实战指南!

茶叶&#xff0c;作为中国传统的饮品&#xff0c;已经深入到了我们的日常生活。 随着生活水平的提升&#xff0c;人们对茶叶的需求也在水涨船高。 面对市场上琳琅满目的新品茶叶&#xff0c;如何让自家品牌脱颖而出&#xff0c;确实是现在头疼的问题。下面给大家分享一些目前…

PLC通信网关有什么功能特点?PLC通信网关工作原理-天拓四方

在工业自动化日益发展的今天&#xff0c;PLC已成为工业控制领域的核心设备。工业自动化与信息化深度融合&#xff0c;PLC的应用日益广泛。PLC通信网关&#xff0c;作为工业物联网的重要组成部分&#xff0c;扮演着连接PLC与云平台的桥梁角色&#xff0c;实现设备间的数据交换与…

Linux多进程和多线程(八)多线程

多线程 线程定义线程与进程线程资源 线程相关命令 pidstat 命令 top 命令ps 命令常见的并发方案 1. 多进程模式2. 多线程模式 创建线程 1. pthread_create() 示例:创建一个线程 2. pthread_exit() 退出线程3. pthread_join() 等待线程结束 示例: 线程分离 创建多个线程 示例 1:…

第二章节:JavaScript 基础

参考:https://blog.csdn.net/2303_78006750/article/details/138022514 **说明:**本章节所介绍的 JavaScript 并不深入,因为在 Web 安全领域不需要对 JavaScript 掌握非常深入,我们只需要能够利用本章节提及到的一些语句对网站进行测试就足够了。 1)JavaScript 简介 01-J…

选择排序(C语言版)

选择排序是一种简单直观的排序算法 算法实现 首先在未排序序列中找到最小&#xff08;大&#xff09;元素&#xff0c;存放到排序序列的起始位置。 再从剩余未排序元素中继续寻找最小&#xff08;大&#xff09;元素&#xff0c;然后放到已排序序列的末尾。 重复第二步&…

MySQL GROUP_CONCAT 函数详解与实战应用

提示&#xff1a;在需要将多个值组合成一个列表时&#xff0c;GROUP_CONCAT() 函数为 MySQL 提供了一种强大的方式来处理数据 文章目录 前言什么是 GROUP_CONCAT()基本语法 示例使用 GROUP_CONCAT()去除重复值排序结果 前言 提示&#xff1a;这里可以添加本文要记录的大概内容…

Jmeter在信息头中设置Bearer与 token 的拼接值

思路&#xff1a;先获取token&#xff0c;将token设置成全局变量&#xff0c;再与Bearer拼接。 第一步&#xff1a;使用提取器将token值提取出来&#xff0c;使用setProperty函数将提取的token值设置成全局变量&#xff0c;在登录请求后面添加BeanShell取样器 或者 BeanShell后…

【work】AI八股-神经网络相关

Deep-Learning-Interview-Book/docs/深度学习.md at master amusi/Deep-Learning-Interview-Book GitHub 网上相关总结&#xff1a; 小菜鸡写一写基础深度学习的问题&#xff08;复制大佬的&#xff0c;自己复习用&#xff09; - 知乎 (zhihu.com) CV面试问题准备持续更新贴 …

昇思25天学习打卡营第21天|LSTM+CRF序列标注

1. 学习内容复盘 概述 序列标注指给定输入序列&#xff0c;给序列中每个Token进行标注标签的过程。序列标注问题通常用于从文本中进行信息抽取&#xff0c;包括分词(Word Segmentation)、词性标注(Position Tagging)、命名实体识别(Named Entity Recognition, NER)等。以命名…

Linux|背景 环境搭建

目录 一、简述Linux发展史 1.1计算机的诞生 1.2操作系统的诞生 1.3Linux操作系统开源 1.4Linux发行版本 二、搭建Linux环境 三、使用shell远程登入到Linux 一、简述Linux发展史 可能大家未听说过Linux&#xff0c;或者只知道它是一个搭配在计算机上的操作系统&#xff0…

【刷题汇总 -- 求最小公倍数、数组中的最长连续子序列、字母收集】

C日常刷题积累 今日刷题汇总 - day0081、求最小公倍数1.1、题目1.2、思路1.3、程序实现 -- 穷举法1.2、程序实现 -- 辗转相除法 2、数组中的最长连续子序列2.1、题目2.2、思路2.3、程序实现 3、字母收集3.1、题目3.2、思路3.3、程序实现 4、题目链接 今日刷题汇总 - day008 1、…

02day-C++学习(const 指针与引用的关系 inline nullptr)

02day-C学习 1. 使用const注意事项 注意事项 • 可以引⽤⼀个const对象&#xff0c;但是必须⽤const引⽤。const引⽤也可以引⽤普通对象&#xff0c;因为对象的访 问权限在引⽤过程中可以缩⼩&#xff0c;但是不能放⼤。 • 不需要注意的是类似 int& rb a3; double d 1…