343. 整數(shù)拆分

設(shè)dp[i]表示拆分 數(shù)字i 出來的正整數(shù)相乘值最大的值

(i - j) * j,和dp[i - j] * j是獲得dp[i]的兩種乘法，在里面求最大值可以得到當(dāng)前dp[i]的最大值，但是這一次的得出的最大值如果賦值給dp[i]，可能沒有沒賦值的dp[i]大，具體例子的話，沒想，只能說是覆蓋了可能出現(xiàn)的問題。

所以是，dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

初始化，dp[0]=0,dp[1]=1或者dp[2]=1都可以，我覺得初始化dp[2]=1比較合適一些，同意卡哥的看法。

先便利要求的 i，然后再遍歷 求最大值的 j

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; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}};

96.不同的二叉搜索樹

二叉搜索樹是一個(gè)有序樹。

• 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
• 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
• 它的左、右子樹也分別為二叉排序樹

設(shè)dp[i]的含義是以1....到 i 構(gòu)成的二叉搜索樹為dp[i]種。

dp[i]該怎么從其他狀態(tài)推出來呢？

聯(lián)系起n=1和n=2與n=3之間構(gòu)成的不同的二叉搜索數(shù)的數(shù)量關(guān)系。（很抽象我也不知道怎么聯(lián)系起來的）

抽象后發(fā)現(xiàn)dp[i]=以1.....到i的各個(gè)節(jié)點(diǎn)為頭節(jié)點(diǎn)的不同二叉搜索樹之和

比如dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]，分別以1，2，3為頭節(jié)點(diǎn)的不同二叉搜索樹的數(shù)量加起來等于 以1....到 i 構(gòu)成的二叉搜索樹 總數(shù) .

最后再抽象一層變成：（j從1開始）

dp[i] += dp[j - 1] * dp[i - j];

?初始化，依照二叉搜索樹的定義，沒有一個(gè)節(jié)點(diǎn)也可以算是二叉搜索樹，所以

 dp[0] = 1;

?最后代碼

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

?i 算從1開始推到i的dp[i]

?j 算從每一階段的dp[i]內(nèi)的1....i位置的不同頭節(jié)點(diǎn)二叉搜索樹之和，然后求出那個(gè)階段的dp[i]