代码随想录Day34 | 62.不同路径,63.不同路径II,343.整数拆分,96.不同的二叉搜索树

ops/2025/1/23 20:18:10/

代码随想录Day34 | 62.不同路径,63.不同路径II,343.整数拆分,96.不同的二叉搜索树

62.不同路径

动态规划第二集:

比较标准简单的一道动态规划,状态转移方程容易想到

难点在于空间复杂度的优化,详见代码

java">class Solution {public int uniquePaths(int m, int n) {// 标准的动态规划int[][] dp = new int[m + 1][n + 1];// 初始化时多加了一行一列,方便初始化dp[1][0] = 1;for (int i = 1; i < dp.length; i++) {for (int j = 1; j < dp[0].length; j++) {// 状态转移方程dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}}return dp[m][n];}
}class Solution {public int uniquePaths(int m, int n) {// 标准的动态规划,空间优化版int[] dp = new int[n + 1];dp[1] = 1;for (int i = 1; i <= m; i++) {for (int j = 2; j <= n; j++) {// 状态转移方程// 只需要第 i 行与第 i-1 行的数据// dp[j - 1]已更新,是第 i 行的数据// dp[j]未更新,是第 i-1 行的数据dp[j] = dp[j - 1] + dp[j];}}return dp[n];}
}

63.不同路径II

相比上题只多了一个障碍的判断

java">class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;// 空间优化思路同62题int[] dp = new int[n + 1];dp[1] = 1;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 处理障碍情况if (obstacleGrid[i - 1][j - 1] == 1)dp[j] = 0;// 状态转移方程else dp[j] = dp[j - 1] + dp[j];}}return dp[n];}
}

343.整数拆分

动态规划问题,相对简单,想清楚状态转移方程就好,详见代码注释

java">class Solution {public int integerBreak(int n) {// dp[i] 的定义是 对 i 进行划分后的最大乘积int[] dp = new int[n + 1];dp[2] = 1;// 动态规划for (int i = 3; i <= n; i++) {// 循环进行划分for (int j = 1; j <= i / 2; j++) {// 状态转移方程// j * dp[i - j] 相当于是 在 i-j 中进行了多次划分// j * (i - j) 是只划分一次dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));}}return dp[n];}
}

96.不同的二叉搜索树

动态规划

要注意到,二叉树种类数目 = 左子树种类数目 * 右子树种类数目

java">class Solution {public int numTrees(int n) {// dp[i]定义为 i个节点时,互不相同的BST的种类数int[] dp = new int[n + 1];// 初始化:0个节点时只有一种dp[0] = 1;for (int i = 1; i <= n ; i++) {// 循环选择根节点为 jfor (int j = 1; j <= i; j++) {// dp[j - 1]为左子树种类数,dp[i - j]为右子树种类数// 左右数目相乘即为根节点为 j 时的种类数// 累加到 dp[i] 上dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
}

http://www.ppmy.cn/ops/150421.html

相关文章

MyBatis-Plus 逆向工程原理及使用指南

概述 MyBatis-Plus&#xff08;简称 MP&#xff09;是 MyBatis 的增强工具&#xff0c;它简化了开发人员对数据库的操作&#xff0c;并提供了代码生成器、分页插件等功能。其中的代码生成器&#xff08;即逆向工程&#xff09;&#xff0c;能够根据数据库中的表结构自动生成实…

【微服务】面试题 6、分布式事务

分布式事务面试题讲解 一、问题背景与解决方案概述 因微服务项目涉及远程调用可能引发分布式事务问题&#xff0c;需解决。主流解决方案有阿里 Seata 框架&#xff08;含 XA、AT、TCC 模式&#xff09;和 MQ。 二、Seata 框架关键角色 事务协调者&#xff08;TC&#xff09;&…

【Ubuntu与Linux操作系统:九、Shell编程】

第9章 Shell编程 9.1 Shell编程基本步骤 Shell编程是一种通过编写脚本文件&#xff0c;使用Shell解释器执行批处理任务的方法。基本步骤如下&#xff1a; 1. 确定需求 在编写脚本之前&#xff0c;明确要实现的功能&#xff0c;例如文件备份、日志分析或自动化部署等。需求的清…

矩阵Strassen 算法

Strassen 算法 不要与多项式乘法的 Schnhage-Strassen 算法混淆。 在线性代数中&#xff0c;以 Volker Strassen 命名的 Strassen 算法是一种矩阵乘法算法。对于大型矩阵&#xff0c;它比标准矩阵乘法算法更快&#xff0c;具有更好的渐近复杂度&#xff0c;尽管朴素算法通常更适…

59_Redis键值设计

1.拒绝BigKey BigKey通常以Key的大小和Key中成员的数量来综合判定。例如: Key本身的数据量过大:一个String类型的Key,它的值为5MB。Key中的成员数过多:一个ZSET类型的Key,它的成员数量为10000个。Key中成员的数据量过大:一个Hash类型的Key,它的成员数量虽然只有1000个但…

ref() 和 reactive() 区别

ref() 和 reactive() 都是 Vue 3 中用于创建响应式数据的方法&#xff0c;但它们之间存在一些关键差异。 首先&#xff0c;ref() 用于创建响应式的标量值&#xff0c;比如数字、字符串、布尔值等基本数据类型&#xff0c;以及对象和数组等复杂数据类型。当你使用 ref() 时&…

了解Webpack:现代前端开发的静态模块打包器

在现代前端开发中&#xff0c;Webpack已成为不可或缺的工具之一。作为一个静态模块打包器&#xff08;module bundler&#xff09;&#xff0c;Webpack通过分析和处理项目中的资源依赖关系&#xff0c;将它们打包成一个或多个bundle&#xff08;捆绑包&#xff09;&#xff0c;…

【Linux】9.Linux第一个小程序进度条

文章目录 Linux第一个小程序&#xff0d;进度条相关知识创建程序1. 程序原理2. 基础程序原理实现 井号进度条代码实现箭头进度条代码实现多重进度条代码实现 Linux第一个小程序&#xff0d;进度条 相关知识 特殊符号&#xff1a; $ 和 $^ 回车换行&#xff1a; 回车和换行其实…