思路：其實(shí)本題的難點(diǎn)就在于如何進(jìn)行遍歷和遞推公式應(yīng)該如果推導(dǎo)，通過(guò)提示的用例我們可以發(fā)現(xiàn)有的n拆分后需要有兩個(gè)數(shù)相乘，有的n拆分后需要有3個(gè)n甚至更多個(gè)n相乘，那么作為一道動(dòng)態(tài)規(guī)劃的題目，很明顯我們應(yīng)該設(shè)置dp[i]為i拆分后的最大乘積，那么我們就應(yīng)該找到dp[i]的上一個(gè)狀態(tài)是什么，如果我們要把一個(gè)數(shù)i拆分成兩部分計(jì)算最大乘積，那么我們?cè)O(shè)其中一個(gè)數(shù)為j，那么另一個(gè)數(shù)就為i-j.乘積就為i（i-j）
那么在本題中也是同理，dp[i]可以有多個(gè)拆分部分組成，我們可以把多個(gè)部分看成兩個(gè)部分來(lái)處理，設(shè)其中一個(gè)數(shù)為j，剩下的所有部分為dp[i-j]，其中dp[i-j]表示其他部分相乘的最大值，我們?cè)陔p重遍歷中不斷計(jì)算和判斷 jdp[i-j]和j*(i-j)的大小，最終得到結(jié)果dp[n]就是題目所求的值

class Solution {
    public int integerBreak(int n) {
//        創(chuàng)建dp數(shù)組
        int[] dp = new int[n+1];
//        dp數(shù)組的初始化
//        dp[0]和dp[1]都是無(wú)意義的 因?yàn)闊o(wú)法拆分 直接從2開始
        dp[2] = 1;
//        遍歷dp數(shù)組
        for (int i = 3; i <= n;i++){
            for (int j = 1; j <= i-j; j++){
//                遞推公式 dp[i-j]表示可能有多個(gè)數(shù)相乘得到的結(jié)果 (i-j)則是單獨(dú)的一個(gè)數(shù)
//dp[i]在這里起到更新最大值的作用
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

思路：本題關(guān)鍵在于遞推關(guān)系的推導(dǎo)，手動(dòng)模擬最初的幾種情況之后，我們可以發(fā)現(xiàn)例子dp[3]中 dp[3]等于元素1為頭結(jié)點(diǎn)搜索樹的數(shù)量 + 元素2為頭結(jié)點(diǎn)搜索樹的數(shù)量 + 元素3為頭結(jié)點(diǎn)搜索樹的數(shù)量。則拓展到dp[i]中對(duì)于第i個(gè)節(jié)點(diǎn)，需要考慮1作為根節(jié)點(diǎn)直到i作為根節(jié)點(diǎn)的所有搜索樹的累加和，所有我們可以用小于i的j來(lái)進(jìn)行遍歷，計(jì)算dp[j]的值，再進(jìn)行累加得到dp[i]

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
//        空樹
        dp[0] = 1;
//      //對(duì)于第i個(gè)節(jié)點(diǎn)，需要考慮1作為根節(jié)點(diǎn)直到i作為根節(jié)點(diǎn)的情況，所以需要累加
        for (int i = 1; i <= n;i++){
//            用j來(lái)表示 小于i的元素作為節(jié)點(diǎn)的情況
            for (int j = 1;j <=i; j++){
//                對(duì)于根節(jié)點(diǎn)j
//                dp[j-1] 代表左子樹的搜索樹數(shù)量
//                dp[i-j] 代表右子樹的搜索樹數(shù)量
//                dp[j - 1] * dp[i-j]表示單個(gè)元素為頭節(jié)點(diǎn)時(shí)構(gòu)成的搜索樹數(shù)量
                dp[i] += dp[j - 1] * dp[i-j];
            }
        }
        return dp[n];
    }
}