1. 代碼隨想錄-動規(guī)8.LC343整數(shù)拆分

題目鏈接
dp數(shù)組含義：dp[i]表示拆分i的最大乘積
遞推公式：dp[i]= max(j*(i-j), j*dp[i-j], dp[i])
解釋：從1遍歷j，有兩種渠道得到dp[i].
一個是j * (i - j) 直接相乘。
一個是j * dp[i - j]，相當(dāng)于是拆分(i - j)
為何不拆分j：j是從1開始遍歷，拆分j的情況，在遍歷j的過程中其實(shí)都計算過了
比如：dp[7]拆分3和dp[4]，為什么不拆分3？因?yàn)閐p[7]拆成1和dp[6]的時候就已經(jīng)拆3了（1+2+4）
初始化：dp[0] = 0; dp[1] = 0; dp[2] = 1;
遍歷終止條件：
拆分一個數(shù)n 使之乘積最大，那么一定是拆分成m個近似相同的子數(shù)相乘才是最大的。
例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的話 也是拆成m個近似數(shù)組的子數(shù)相乘才是最大的，也就是：最差也應(yīng)該是拆成兩個相同的 可能是最大值。
那么 j 遍歷，只需要遍歷到 n/2 就可以，后面就沒有必要遍歷了，一定不是最大值。
比如10的拆分最大值最差也是拆成5和5，再拆的細(xì)、貼合就是334，但如果從6往后遍歷的話，只會越來越加大每個子數(shù)之間的差距，不會達(dá)到拆成5和5的結(jié)果。所以沒必要遍歷n/2之后的數(shù)了。

代碼：

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

坑：
內(nèi)for循環(huán)中，j <= i/2;而不是<；
Math.max()里面的參數(shù)數(shù)量只能是2

2. 代碼隨想錄-動規(guī)9.LC96不同的二叉搜索樹

題目鏈接
dp數(shù)組含義：dp[i]表示由i個節(jié)點(diǎn)組成二叉搜索樹的種數(shù)
遞推公式：
n為2時，頭節(jié)點(diǎn)為1，有1種方式；頭節(jié)點(diǎn)為2，有1種方式。

n為3時，種數(shù)等于頭節(jié)點(diǎn)為1的種數(shù)+頭節(jié)點(diǎn)為2的種數(shù)+頭節(jié)點(diǎn)為3的種數(shù)
頭節(jié)點(diǎn)為1的種數(shù) = dp[0] * dp[2]，左子數(shù)無，右子樹2個節(jié)點(diǎn)
頭節(jié)點(diǎn)為2的種數(shù) = dp[1] * dp[1]，左子樹1個節(jié)點(diǎn)，右子樹1個節(jié)點(diǎn)
頭節(jié)點(diǎn)為3的種數(shù) = dp[2] * dp[0]，左子樹2個節(jié)點(diǎn)，右子樹無

所以，公式為：
dp[i] += dp[j-1] * dp[i-j];
從1遍歷j，直到i
初始化：dp[0] = 1; dp[1] = 1;

代碼：

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

思考：學(xué)會分類很重要。分對類了事半功倍！文章來源地址http://www.zghlxwxcb.cn/news/detail-782262.html

到了這里，關(guān)于【每日刷題】動態(tài)規(guī)劃-代碼隨想錄動規(guī)-8、9的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！