动态规划02(Leetcode62、63、343、96)

2024-06-22 15:20
文章标签 动态 规划 02 96 63 343 leetcode62

本文主要是介绍动态规划02(Leetcode62、63、343、96),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考资料:

https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html

62. 不同路径

题目描述:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:

输入:m = 3, n = 7
输出:28

思路分析:

本题思路简单,按照动规五步即可实现。

状态压缩:二维 ——> 一维

代码实现:

//动规
//1.dp[i][j]:到达点(i,j)的路径数
class Solution {public int uniquePaths(int m, int n) {int[][] dp=new int [m][n];//3.初始化for(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++){//列//2.递推公式dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];        }
}//状态压缩
class Solution {public int uniquePaths(int m, int n) {int[] dp=new int[n];Arrays.fill(dp,1);//第一行只有一条路径到for(int i=1;i<m;i++){for(int j=1;j<n;j++){//第一列也只有一条路dp[j]+=dp[j-1];//dp[j]=dp[j](上方来)-dp[j-1](左边来)}}return dp[n-1];}
}

 63. 不同路径 II

题目描述:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

思路分析:

整体思路与上题一样。

区别:本题在初始化和遍历过程中增加障碍物的条件判断即可。

代码实现:

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m=obstacleGrid.length;int n=obstacleGrid[0].length;int[][] dp=new int[m][n];if(obstacleGrid[m-1][n-1]==1 || obstacleGrid[0][0]==1) return 0;for(int i=0;i<m && obstacleGrid[i][0]==0;i++){dp[i][0]=1;}for(int j=0;j<n&&obstacleGrid[0][j]==0;j++){dp[0][j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==1){dp[i][j]=0;continue;}dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}//压缩
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m=obstacleGrid.length;int n=obstacleGrid[0].length;int[] dp=new int[n];for(int j=0;j<n&&obstacleGrid[0][j]==0;j++){//第一行dp[j]=1;}for(int i=1;i<m;i++){for(int j=0;j<n;j++){if(obstacleGrid[i][j]==1){dp[j]=0;}else if(j!=0){dp[j]+=dp[j-1];}}}return dp[n-1];}
}

343. 整数拆分

题目描述:

给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

思路分析:

状态转移方程=拆成2个数 + 拆成3个数及以上

初始化 dp[2]=1 

优化:j 遍历到 i/2 即可,再往后就重复遍历了

代码实现:

//dp[i]:数i拆分后的数乘积最大值为dp[i]
class Solution {public int integerBreak(int n) {if(n==2) return 1;int[] dp=new int[n+1];dp[2]=1;for(int i=3;i<=n;i++){for(int j=1;j<=i/2;j++){dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));//j*(i-j)拆成两数//j*dp[i-j]拆成两数以上}}return dp[n];}
}

96. 不同的二叉搜索树

题目描述:

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

示例 1:

输入:n = 3
输出:5

思路分析:

初始化:空节点对应一种情况,1个节点对应一种情况

递推公式:头结点从1到n遍历,将每个情况相加

代码实现:

class Solution {public int numTrees(int n) {if(n==1) return 1;int[] dp=new int[n+1];dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){//以j为头结点dp[i]+=dp[j-1]*dp[i-j];//左*右}}return dp[n];}
}

这篇关于动态规划02(Leetcode62、63、343、96)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

Git 的特点—— Git 学习笔记 02

文章目录 Git 简史Git 的特点直接记录快照,而非差异比较近乎所有操作都是本地执行保证完整性一般只添加数据 参考资料 Git 简史 众所周知,Linux 内核开源项目有着为数众多的参与者。这么多人在世界各地为 Linux 编写代码,那Linux 的代码是如何管理的呢?事实是在 2002 年以前,世界各地的开发者把源代码通过 diff 的方式发给 Linus,然后由 Linus

轨迹规划-B样条

B样条究竟是干啥的?白话就是给出一堆点,用样条的方式,给这些点连接起来,并保证丝滑的。 同时B样条分为准均匀和非均匀,以下为准均匀为例。 参考链接1:https://zhuanlan.zhihu.com/p/50626506https://zhuanlan.zhihu.com/p/50626506 参考链接2: https://zhuanlan.zhihu.com/p/536470972h

PMBOK® 第六版 规划进度管理

目录 读后感—PMBOK第六版 目录 规划进度管理主要关注为整个项目期间的进度管理提供指南和方向。以下是两个案例,展示了进度管理中的复杂性和潜在的冲突: 案例一:近期,一个长期合作的客户因政策要求,急需我们为多家医院升级一个小功能。在这个过程中出现了三个主要问题: 在双方确认接口协议后,客户私自修改接口并未通知我们,直到催进度时才发现这个问题关于UI设计的部分,后台开发人员未将其传递给

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划