代码随想录算法训练营Day 41| 动态规划part03 | 343. 整数拆分、96.不同的二叉搜索树

代码随想录算法训练营Day 41| 动态规划part03 | 343. 整数拆分、96.不同的二叉搜索树

---

---

343. 整数拆分

题目链接

1. 确定dp数组以及下标的含义
   dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
2. 确定递推公式
   想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]
   状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
3. 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;
4. 确定遍历顺序
   看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
5. 打印dp数组

一、动态规划

class Solution(object):def integerBreak(self, n):""":type n: int:rtype: int"""dp=[0]*(n+1)dp[1]=1dp[2]=1for i in range(3,n+1):for j in range(1,i): # 优化版本可以写为 for j in range(1,i//2+1)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时，只有一种拆分方式：1+1=2，乘积为1return 1if n == 3:  # 当n等于3时，只有一种拆分方式：2+1=3，乘积为2return 2if n == 4:  # 当n等于4时，有两种拆分方式：2+2=4和1+1+1+1=4，乘积都为4return 4result = 1while n > 4:result *= 3  # 每次乘以3，因为3的乘积比其他数字更大n -= 3  # 每次减去3result *= n  # 将剩余的n乘以最后的结果return result

---

96.不同的二叉搜索树

题目链接

1. 确定dp数组以及下标的含义
   dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]
2. 确定递推公式
   ， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
   j相当于是头结点的元素，从1遍历到i为止。
   所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
3. dp数组如何初始化
   d从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树
   从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
   所以初始化dp[0] = 1
4. 确定遍历顺序
   首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
5. 打印dp数组

一、动态规划

class Solution(object):def numTrees(self, n):""":type n: int:rtype: int"""dp=[0]*(n+1)dp[0]=1 # 当n为0时，只有一种情况，即空树，所以dp[0] = 1for i in range(2,n+1):# 遍历从1到n的每个数字for j in range(1,i+1): # 对于每个数字i，计算以i为根节点的二叉搜索树的数量dp[i] += dp[j-1]*dp[i-j] # 利用动态规划的思想，累加左子树和右子树的组合数量return dp[n]