【动态规划算法题记录】343. 整数拆分 | 96.不同的二叉搜索树
整数拆分
题目🔗
题目描述
给定一个正整数 n ，将其拆分为 k个正整数的和（k >= 2），并使这些整数的乘积最大化。
返回你可以获得的最大乘积 。
思路分析
- dp数组含义：
dp[i]表示整数i拆分后的最大乘积。 - 递推公式：
dp[i] = j * dp[i - j] - dp数组初始化：
dp[0] = 0, dp[1] = 0, dp[2] = 1
cpp代码
class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);dp[0] = 0;dp[1] = 0;dp[2] = 1;for(int i = 3; i <= n; ++i){for(int j = 1; j <= i/2; ++j){dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));}}return dp[n];}
};
不同的二叉搜索树
题目🔗
题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
思路分析
- dp数组含义：
dp[i]表示由i个节点组成的不同二叉搜索树的数量。 - 递推公式：从上图我们可以发现，
dp[3] = 以1为头节点的二叉树数量+以2为头节点的二叉树数量+以3为头节点的二叉树数量
其中，
以1为头节点的二叉树数量 = 右子树有2个元素的搜索树数量 * 左元素有0个元素的搜索树数量
以2为头节点的二叉树数量 = 右子树有1个元素的搜索树数量 * 左元素有1个元素的搜索树数量
以3为头节点的二叉树数量 = 右子树有2个元素的搜索树数量 * 左元素有0个元素的搜索树数量
而，
有2个元素的搜索树数量 = dp[2]
有1个元素的搜索树数量 = dp[1]
有0个元素的搜索树数量 = dp[0]
因此可以推断出： d p [ i ] = d p [ j − 1 ] ∗ d p [ i − j ] dp[i] = dp[j - 1] * dp[i - j] dp[i]=dp[j−1]∗dp[i−j] - dp数组初始化：
dp[0] = 1
cpp代码
class Solution {
public:int numTrees(int n) {vector<int> dp(n+1);dp[0] = 1;for(int i = 1; i <= n; ++i){for(int j = 1; j <= i; ++j){dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
};
总结
这两题都是属于思路比较绕，但想清楚之后会发现很简单的，所以前期一定要理解dp数组的相关含义。