电子商务网站建设方案书的总结,商城推广 网站建设,易云巢做网站公司,做电影下载网站好62. 不同路径
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish” #xff09;。
问总共有多少条不同的路径…62. 不同路径
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径 题目链接LeetCode62.不同路径 文档讲解代码随想录LeetCode62.不同路径 题解
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(n, 0));for (int i 0; i m; i)dp[i][0] 1;for (int j 0; j n; j)dp[0][j] 1;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];}}return dp[m - 1][n - 1];}
};时间复杂度O(mn)空间复杂度O(mn) 63. 不同路径II
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示。 题目链接LeetCode63.不同路径II 文档讲解代码随想录LeetCode63.不同路径II 题解 当路径上出现障碍时dp数组对应位置的值保持不变为0 class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();vectorvectorint dp(m, vectorint(n, 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)continue;dp[i][j] dp[i - 1][j] dp[i][j - 1];}}return dp[m - 1][n - 1];}
};时间复杂度O(mn)空间复杂度O(mn) 343. 整数拆分
给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。 题目链接LeetCode343.整数拆分 文档讲解代码随想录LeetCode343.整数拆分 题解 分拆数字 i 可以得到的最大乘积为dp[i]遍历过程中的递推公式为dp[i] max(dp[i], max(j * (i - j), j * dp[i - j])) class Solution {
public:int integerBreak(int n) {vectorint dp(n 1);dp[2] 1;for (int i 3; i n; i) {for (int j 1; j i; j) {dp[i] max(dp[i], max(j * (i - j), j * dp[i - j]));}}return dp[n];}
};时间复杂度O(n^2)空间复杂度O(n) 96. 不同的二叉搜索树
给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 题目链接LeetCode96.不同的二叉搜索树 文档讲解代码随想录LeetCode96.不同的二叉搜索树 题解 dp[i]为利用 i 个节点可以得到的不同二叉搜索树的种数以n3为例dp[3] 元素1为头节点搜索树的数量 元素2为头节点搜索树的数量 元素3为头节点搜索树的数量。 元素1为头节点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量 元素2为头节点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量 元素3为头节点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量 class Solution {
public:int numTrees(int n) {vectorint dp(n 1);dp[0] 1;dp[1] 1;for (int i 2; i n; i) {for (int j 0; j i; j) {dp[i] dp[j] * dp[i - j - 1];}}return dp[n];}
};时间复杂度O(n^2)空间复杂度O(n)
