那个软件可以做网站,设计素材网站解析,临沂seo建站,网站制作帐户设置代码随想录算法训练营Day 41| 动态规划part03 | 343. 整数拆分、96.不同的二叉搜索树 文章目录 代码随想录算法训练营Day 41| 动态规划part03 | 343. 整数拆分、96.不同的二叉搜索树343. 整数拆分一、动态规划二、贪心#xff08;不需要掌握#xff09; 96.不同的二叉搜索树一…代码随想录算法训练营Day 41| 动态规划part03 | 343. 整数拆分、96.不同的二叉搜索树 文章目录 代码随想录算法训练营Day 41| 动态规划part03 | 343. 整数拆分、96.不同的二叉搜索树343. 整数拆分一、动态规划二、贪心不需要掌握 96.不同的二叉搜索树一、动态规划 343. 整数拆分
题目链接 确定dp数组以及下标的含义 dp[i]分拆数字i可以得到的最大乘积为dp[i]。确定递推公式 想要求dp[i][j]只能有两个方向来推导出来即dp[i - 1][j] 和 dp[i][j - 1] 状态转移方程 dp[i][j] dp[i - 1][j] dp[i][j - 1];dp数组如何初始化 dp[i][0]一定都是1因为从(0, 0)的位置到(i, 0)的路径只有一条那么dp[0][j]也同理; for (int i 0; i m; i) dp[i][0] 1; for (int j 0; j n; j) dp[0][j] 1;确定遍历顺序 看一下递推公式dp[i][j] dp[i - 1][j] dp[i][j - 1]dp[i][j]都是从其上方和左方推导而来那么从左到右一层一层遍历就可以了。打印dp数组 一、动态规划
class Solution(object):def integerBreak(self, n)::type n: int:rtype: intdp[0]*(n1)dp[1]1dp[2]1for i in range(3,n1):for j in range(1,i): # 优化版本可以写为 for j in range(1,i//21)dp[i]max(j*dp[i-j],j*(i-j),dp[i])return dp[n]二、贪心不需要掌握
class Solution:def integerBreak(self, n):if n 2: # 当n等于2时只有一种拆分方式112乘积为1return 1if n 3: # 当n等于3时只有一种拆分方式213乘积为2return 2if n 4: # 当n等于4时有两种拆分方式224和11114乘积都为4return 4result 1while n 4:result * 3 # 每次乘以3因为3的乘积比其他数字更大n - 3 # 每次减去3result * n # 将剩余的n乘以最后的结果return result96.不同的二叉搜索树
题目链接 确定dp数组以及下标的含义 dp[i] 1到i为节点组成的二叉搜索树的个数为dp[i]确定递推公式 dp[i] dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] j相当于是头结点的元素从1遍历到i为止。 所以递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为j为头结点左子树节点数量i-j 为以j为头结点右子树节点数量dp数组如何初始化 d从定义上来讲空节点也是一棵二叉树也是一棵二叉搜索树 从递归公式上来讲dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0也需要dp[以j为头结点左子树节点数量] 1 否则乘法的结果就都变成0了。 所以初始化dp[0] 1确定遍历顺序 首先一定是遍历节点数从递归公式dp[i] dp[j - 1] * dp[i - j]可以看出节点数为i的状态是依靠 i之前节点数的状态。打印dp数组 一、动态规划
class Solution(object):def numTrees(self, n)::type n: int:rtype: intdp[0]*(n1)dp[0]1 # 当n为0时只有一种情况即空树所以dp[0] 1for i in range(2,n1):# 遍历从1到n的每个数字for j in range(1,i1): # 对于每个数字i计算以i为根节点的二叉搜索树的数量dp[i] dp[j-1]*dp[i-j] # 利用动态规划的思想累加左子树和右子树的组合数量return dp[n]
