LeeCode 343. 整数拆分

343. 整数拆分 - 力扣（LeetCode）

动态规划法

思路：

1.确定dp数组及下标含义：dp[i]：分拆数字i，可得到的最大乘积。

2.确定递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

3.dp数组如何初始化：dp[2] = 1；

4.确定遍历顺序：从前向后

for (int i = 3; i <= n; i++) {for (int j = 1; j <= i / 2; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}
}

5.举例递推dp数组

代码：

class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[2] = 1;for (int i = 3; i <= n; i++) {for (int j = 1; j <= i / 2; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}} return dp[n];}
};

时间复杂度：O(n²) 空间复杂度：O(n)

贪心解法

思路：每次拆成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;}
};

时间复杂度：O(n) 空间复杂度：O(1)

LeeCode 96.不同的二叉搜索树

96. 不同的二叉搜索树 - 力扣（LeetCode）

思路：

1.确定dp数组及下标含义：dp[i]：1到i为节点组成的二叉搜索树的个数；

2.确定递推公式：dp[i] += dp[j - 1] * dp[i - j];

3.dp数组如何初始化：dp[0] = 1；

4.确定遍历顺序：遍历 i 里面每一个数作为头结点的状态，用 j 来遍历；

for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}
}

5.举例递推dp数组

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];}
};

时间复杂度：O(n²) 空间复杂度：O(n)