响应式网站好还是自适应网站好,江门建站模板搭建,兰州建设,深圳台历制作62.不同路径
想要求dp[i][j]#xff0c;只能有两个方向来推导出来#xff0c;即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥#xff0c;是从(0, 0)的位置到(i - 1, j)有几条路径#xff0c;dp[i][j - 1]同理。
那么很自然#xff0c;dp[i][j] …62.不同路径
想要求dp[i][j]只能有两个方向来推导出来即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥是从(0, 0)的位置到(i - 1, j)有几条路径dp[i][j - 1]同理。
那么很自然dp[i][j] dp[i - 1][j] dp[i][j - 1]因为dp[i][j]只有这两个方向过来。
class Solution:def uniquePaths(self, m: int, n: int) - int:dp[[0]*n for _ in range(m)]#用来存储唯一路径数#设置第一行和第一列的基本情况for i in range(m):dp[i][0]1for j in range(n):dp[0][j]1#计算每个单元格的唯一路径数for i in range(1,m):for j in range(1,n):dp[i][j]dp[i-1][j]dp[i][j-1]return dp[m-1][n-1]63.不同路径2 其实只要考虑到遇到障碍dp[i][j]保持0就可以了。
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int:mlen(obstacleGrid)#行数nlen(obstacleGrid[0])if obstacleGrid[m-1][n-1]1 or obstacleGrid[0][0]1:#起点和终点有障碍物直接返回return 0dp[[0]*n for _ in range(m)]for i in range(m):if obstacleGrid[i][0]0:#遇到障碍物时直接退出循环后面默认都是0dp[i][0]1else:breakfor j in range(n):if obstacleGrid[0][j]0:dp[0][j]1else:breakfor i in range(1,m):for j in range(1,n):if obstacleGrid[i][j]1:continuedp[i][j]dp[i-1][j]dp[i][j-1]return dp[m-1][n-1]343.整数拆分
dp[i]分拆数字i可以得到的最大乘积为dp[i]
注意 枚举j的时候是从1开始的。从0开始的话那么让拆分一个数拆个0求最大乘积就没有意义了。
至于 “拆分一个数n 使之乘积最大那么一定是拆分成m个近似相同的子数相乘才是最大的”
class Solution:# 假设对正整数 i 拆分出的第一个正整数是 j1 j i则有以下两种方案# 1) 将 i 拆分成 j 和 i−j 的和且 i−j 不再拆分成多个正整数此时的乘积是 j * (i-j)# 2) 将 i 拆分成 j 和 i−j 的和且 i−j 继续拆分成多个正整数此时的乘积是 j * dp[i-j]def integerBreak(self, n):dp [0] * (n 1) # 创建一个大小为n1的数组来存储计算结果dp[2] 1 # 初始化dp[2]为1因为当n2时只有一个切割方式112乘积为1# 从3开始计算直到nfor i in range(3, n 1):# 遍历所有可能的切割点for j in range(1, i // 2 1):# 计算切割点j和剩余部分(i-j)的乘积并与之前的结果进行比较取较大值dp[i] max(dp[i], (i - j) * j, dp[i - j] * j)return dp[n] # 返回最终的计算结果
96.不同的二叉搜索树 来看看n为3的时候有哪几种情况。
当1为头结点的时候其右子树有两个节点看这两个节点的布局是不是和 n 为2的时候两棵树的布局是一样的啊
当3为头结点的时候其左子树有两个节点看这两个节点的布局是不是和n为2的时候两棵树的布局也是一样的啊
当2为头结点的时候其左右子树都只有一个节点布局是不是和n为1的时候只有一棵树的布局也是一样的啊
dp[3]就是 元素1为头结点搜索树的数量 元素2为头结点搜索树的数量 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
所以递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为j为头结点左子树节点数量i-j 为以j为头结点右子树节点数量 左子树肯定时比根少一右子树是要求的减去根就是比他大的
class Solution:def numTrees(self, n: int) - int:dp[0]*(n1)dp[0]1#当n为0时只有一种情况for i in range(1,n1):for j in range(1,i1):dp[i]dp[j-1]*dp[i-j]#以j为头节点的左子树和以j为头节点的右子树return dp[n]
