一、LeetCode343. 整數拆分

題目鏈接：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拆分成k個正整數乘積所能夠得到的最大值。

遞推公式：

用一個j來遍歷從1到i,得到兩個dp[i]，即dp[i]=j*(i-j)(將整數i分成兩個正整數j和i-j),和dp[i]=j*dp[i-j]。

所以dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))。

初始化：

dp[0]和dp[1]初始化沒有意義，所以我們初始化dp[2]=1(2拆分成兩個1相乘)。

遍歷順序：

因為dp[2]已經初始化了，所以我們從3遍歷到n。

代碼如下：

class Solution {public int integerBreak(int n) {int[] dp = new int[n + 1];dp[2] = 1;//初始化for(int i = 3; i <= n; i++) {for(int j = 1; j < i; j++) {dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));}}return dp[n];}
}

時間復雜度o(n^2)，空間復雜度o(n)。

二、LeetCode96. 不同的二叉搜索樹

題目鏈接：96. 不同的二叉搜索樹

題目描述：

給你一個整數?n?，求恰由?n?個節點組成且節點值從?1?到?n?互不相同的?二叉搜索樹?有多少種？返回滿足題意的二叉搜索樹的種數。

示例 1：

輸入：n = 3
輸出：5

示例 2：

輸入：n = 1
輸出：1

提示：

• 1 <= n <= 19

算法分析：

定義dp數組及下標含義：

dp[i]表示i個節點組成的二叉搜索樹的種樹。

遞推公式：

j從1遍歷到i，當j為頭節點時，左子樹有i-1個節點，左子樹的種類數相當于dp[j-1]，右子樹有i-j個節點，右子樹的種類數相當于dp[i-j]。

所以dp[i]+=dp[j-1]*dp[i-j],j從1比那里遍歷到i;

初始化:

dp[0]初始化為1（0的話會影響乘法結果），dp[1]初始化為1（一個節點的二叉搜索樹只有一種情況）

遍歷順序：

i從2遍歷到n，然后確定dp[i](dp[i]+=dp[j-1]*dp[i-j])。

如果結果有誤打印dp數組檢查驗證。

代碼如下：

class Solution {public int numTrees(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++){for(int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
}

時間復雜度o（n^2），空間復雜度o(n)

總結

這兩道題還是比較難的，自己想很難有思路。