一、LeetCode343. 整數(shù)拆分
題目鏈接：343. 整數(shù)拆分
題目描述：
給定一個正整數(shù)?n?，將其拆分為?k?個?正整數(shù)?的和（?k >= 2?），并使這些整數(shù)的乘積最大化。
返回?你可以獲得的最大乘積?。
示例 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數(shù)組及下標含義：
dp[i]表述正整數(shù)i拆分成k個正整數(shù)乘積所能夠得到的最大值。
遞推公式：
用一個j來遍歷從1到i,得到兩個dp[i]，即dp[i]=j*(i-j)(將整數(shù)i分成兩個正整數(shù)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]已經(jīng)初始化了，所以我們從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];
}
}時間復(fù)雜度o(n^2)，空間復(fù)雜度o(n)。
二、LeetCode96. 不同的二叉搜索樹
題目鏈接：96. 不同的二叉搜索樹
題目描述：
給你一個整數(shù)?n?，求恰由?n?個節(jié)點組成且節(jié)點值從?1?到?n?互不相同的?二叉搜索樹?有多少種？返回滿足題意的二叉搜索樹的種數(shù)。
示例 1：
輸入：n = 3 輸出：5
示例 2：
輸入：n = 1 輸出：1
提示：
1 <= n <= 19
算法分析：
定義dp數(shù)組及下標含義：
dp[i]表示i個節(jié)點組成的二叉搜索樹的種樹。
遞推公式：
j從1遍歷到i，當j為頭節(jié)點時，左子樹有i-1個節(jié)點，左子樹的種類數(shù)相當于dp[j-1]，右子樹有i-j個節(jié)點，右子樹的種類數(shù)相當于dp[i-j]。
所以dp[i]+=dp[j-1]*dp[i-j],j從1比那里遍歷到i;
初始化:
dp[0]初始化為1（0的話會影響乘法結(jié)果），dp[1]初始化為1（一個節(jié)點的二叉搜索樹只有一種情況）
遍歷順序：
i從2遍歷到n，然后確定dp[i](dp[i]+=dp[j-1]*dp[i-j])。
如果結(jié)果有誤打印dp數(shù)組檢查驗證。
代碼如下：
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];
}
}時間復(fù)雜度o（n^2），空間復(fù)雜度o(n)文章來源：http://www.zghlxwxcb.cn/news/detail-761482.html
總結(jié)
這兩道題還是比較難的，自己想很難有思路。文章來源地址http://www.zghlxwxcb.cn/news/detail-761482.html
到了這里，關(guān)于LeetCode算法題解（動態(tài)規(guī)劃）|LeetCode343. 整數(shù)拆分、LeetCode96. 不同的二叉搜索樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
