1?343. 整數(shù)拆分

343.?整數(shù)拆分

一開(kāi)始做?沒(méi)有思路，學(xué)習(xí)了題解才，ac代碼：

class Solution {
public:
    int dp[60];  // 含義：i 把它拆分成若干個(gè)數(shù)，這些數(shù)的乘積最大的值
    /*
    很妙這里j的含義 ，如果是我直覺(jué)會(huì)用k作為其中一個(gè)循環(huán) 但不知道是不是要三個(gè)循環(huán)...
    j的含義i的拆分因子： 因?yàn)閗大于等于2 所以至少兩個(gè)因子 所以 j = 1,...,i-1
    dp[i] = max(dp[i], max(j*(i-j) , dp[i-j]*j))
                        拆分成兩個(gè)  拆分2個(gè)以上
    dp[2] = 1;
    i++


    2 3 4 5 6
    1 2 4 
    */
    int integerBreak(int n) 
    {
        dp[2] = 1;
        if(n == 2)return dp[2];

        for(int i = 3; i <= n; i++)
            for(int j = 1; j <= i-1;j++)
                dp[i] = max(dp[i], max(j*(i-j) , dp[i-j]*j));
                
        return dp[n];

    }
};

后來(lái)仔細(xì)看題解，其實(shí) for - j?的次數(shù)可以?xún)?yōu)化——

注意 枚舉j的時(shí)候，是從1開(kāi)始的。從0開(kāi)始的話(huà)，那么讓拆分一個(gè)數(shù)拆個(gè)0，求最大乘積就沒(méi)有意義了。

優(yōu)化1：

j 的結(jié)束條件是 j < i - 1 ，其實(shí) j < i 也是可以的，不過(guò)可以節(jié)省一步，例如讓j = i - 1，的話(huà)，其實(shí)在 j = 1的時(shí)候，這一步就已經(jīng)拆出來(lái)了，重復(fù)計(jì)算，所以 j < i - 1

至于 i是從3開(kāi)始，這樣dp[i - j]就是dp[2]正好可以通過(guò)我們初始化的數(shù)值求出來(lái)。

優(yōu)化2： 更優(yōu)化一步，可以這樣：

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j <= i / 2; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

因?yàn)?span style="color:#fe2c24;">拆分一個(gè)數(shù)n 使之乘積最大，那么一定是拆分成m個(gè)近似相同的子數(shù)相乘才是最大的。

例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的話(huà) 也是拆成m個(gè)近似數(shù)組的子數(shù) 相乘才是最大的。

只不過(guò)我們不知道m(xù)究竟是多少而已，但可以明確的是m一定大于等于2，既然m大于等于2，也就是 最差也應(yīng)該是拆成兩個(gè)相同的 可能是最大值。

那么 j 遍歷，只需要遍歷到 n/2 就可以，后面就沒(méi)有必要遍歷了，一定不是最大值。

至于 “拆分一個(gè)數(shù)n 使之乘積最大，那么一定是拆分成m個(gè)近似相同的子數(shù)相乘才是最大的” 這個(gè)我就不去做數(shù)學(xué)證明了，感興趣的同學(xué)，可以自己證明。

題解的貪心做法：

本題也可以用貪心，每次拆成n個(gè)3，如果剩下是4，則保留4，然后相乘，但是這個(gè)結(jié)論需要數(shù)學(xué)證明其合理性！

2?96. 不同的二叉搜索樹(shù)

96.?不同的二叉搜索樹(shù)

看到題目一開(kāi)始又是懵的，看了題解才知道從n=1 n=2 到n=3可以借助前n=1，n=2推出來(lái)，找到規(guī)律，AC代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-676272.html

class Solution {
public:
    int dp[20];  // 恰由i個(gè)節(jié)點(diǎn)組成的不同的二叉線索樹(shù)最大的數(shù)目
    /*
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]

    for(int j = 1; j <= i; j++)
        dp[i] += dp[j-1]*dp[n-j];
    
    i++

    0 1 2 3 4
    0 1 2 5 

    */
    int numTrees(int n) 
    {
        dp[0] = 1;  // 沒(méi)有實(shí)際含義 為了湊結(jié)果的
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i <= n; i++)
            for(int j = 1;j <= i; j++)
                dp[i] += dp[j-1]*dp[i-j];
        
        return dp[n];
    }
};

到了這里，關(guān)于代碼隨想錄打卡—day41—【DP】— 8.26+27 DP基礎(chǔ)3的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！