Leetcode - 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。
笔记:
按照动规五部曲来思考:
(1)确定dp数组含义:
dp[i]表示拆分整数i的最大成绩和
(2)初始化dp数组:
dp[0] = 0,dp[1] = 1, dp[2] = 1
(3)确定状态转移方程:
由于我们在拆分的时候做选择:一个是我们可以选择两个数来做比较,一个我们可以将被减数在做拆分用被减数的最大字元素乘积,也就是我们可以选择拆掉被减数或者不拆被减数:
dp[i] = max(dp[i],max(dp[i - j] * j + (i - j) * j)
(3)遍历顺序:
从小到大遍历即可
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j < i; j++){
dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
}
}
return dp[n];
}
};
这里我们需要注意的是第二个max才是体现我们动态规划思想的重要一步。
为什么不拆分j呢;因为j的拆分已经在第一层for循环求过了。
Leetcode - 96:不同的二叉搜索树
题目:
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3 输出:5
示例 2:
输入:n = 1 输出:1
笔记:
这道题是真的难,
(1)确定dp数组含义:dp[i]表示i个元素的二叉搜索树的种类。
(2)初始化,dp[0] = 1
(3)状态转移方程:这里我们用到了两层循环,外层循环是求目标数,内层循环是选取不同的节点作为头结点,各自的搜索树数量。以m为头结点的搜索树,其左子树有m-1个元素,其右节点有n-m个(减去头节点)。然后因为是求组合数所以两者相乘即得。
dp[i] += dp[j - 1] * dp[i - j];
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1, 0);
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];
}
};