-爱代码爱编程
_35LeetCode代码随想录算法训练营第三十五天-动态规划
题目列表
- 343.整数拆分
- 96.不同的二叉搜索树
代码随想录地址
https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
343.整数拆分
题目
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
思路
动态规划五部曲
- 确定dp数组以及其下标的含义
dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
- 递推公式
递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
dp[i]：为什么与它比，因为每一次都更新要更新dp[i]，要选择最大的存到dp[i]的。
(i - j) * j：将数字拆分为两个数字相乘。
dp[i - j] * j：将数字拆分为三个及以上的数字相乘。为什么不拆分j，因为在遍历过程种j的所有可能都包含了。
- 初始化dp数组
dp[0] = 0;dp[1] = 0;dp[2] = 1。
但是本题中，只给dp[2]赋值为1。
- 遍历顺序
从前往后遍历。
代码
动态规划
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
/*
* @lc app=leetcode.cn id=343 lang=cpp
*
* [343] 整数拆分
*/
// @lc code=start
class Solution {
public:
int integerBreak(int n) {
//定义dp数组
vector<int> dp(n + 1, 0);
//初始化dp数组
dp[2] = 1;
//遍历求得最大乘积
for(int i = 3; i <= n; i++)
for(int j = 1; j <= i/2; j++)//为什么要只遍历到i/2, 因为要求得乘积最大值，要求拆分的数越相近越好，j越大，就越偏离最大乘积
dp[i] = max({dp[i], j * (i - j), j * dp[i - j]});
return dp[n];
}
};
// @lc code=end
贪心
- 时间复杂度：O(n)
- 空间复杂度：O(1)
每次拆成n个3，如果剩下是4，则保留4，然后相乘，但是这个结论需要数学证明其合理性！
class Solution {
public:
int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
if (n == 4) return 4;
int result = 1;
while (n > 4) {
result *= 3;
n -= 3;
}
result *= n;
return result;
}
};
96.不同的二叉搜索树
题目
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
思路
思考
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
动态规划五部曲
- 确定dp数组（dp table）以及下标的含义
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数组如何初始化
dp[0] = 1;//表示0个节点也是二叉搜索树，一种情况
其他的可以根据递推公式推导出来。
- 遍历顺序
从左往右的遍历顺序。
代码
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)
- 空间复杂度： O ( n ) O(n) O(n)
/*
* @lc app=leetcode.cn id=96 lang=cpp
*
* [96] 不同的二叉搜索树
*/
// @lc code=start
class Solution {
public:
int numTrees(int n) {
//定义dp数组及其初始化
//i个不同元素节点组成的二叉搜索树的个数为dp[i]
vector<int> dp(n + 1, 0);
//dp[0] = 1;//表示0个节点也是二叉搜索树，一种情况,其他的可以根据递推公式推导出来。
dp[0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j < i; j++)//左面有j个节点
dp[i] += dp[j] * dp[i - j - 1];
//dp[i - j - 1]是指右面有i - j - 1个节点
return dp[n];
}
};
// @lc code=end