代碼隨想錄算法訓練營第四十一天|343. 整數拆分、96.不同的二叉搜索樹

整數拆分

343. 整數拆分
文章講解：https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
題目鏈接：https://leetcode.cn/problems/integer-break/
視頻講解：https://www.bilibili.com/video/BV1Mg411q7YJ/

自己看到題目的第一想法

看完代碼隨想錄之后的想法

解題思路：盡量把數字拆成相同的數。
整體還是走動態規劃五步驟：

• 確定dp數組以及下標的含義
  • dp[i]：分拆數字i，可以得到的最大乘積為dp[i]
• 確定遞推公式
  • 如果是求最大積的話從1遍歷j，有兩種渠道得到dp[i]。一個是j*(i - j)直接相乘；一個是jdp[i - j]，相當于拆分(i - j)。可以這么理解，j(i - j) 是單純的把整數拆分為兩個數相乘，而j * dp[i - j]是拆分成兩個以及兩個以上的個數相乘。所以遞推公式：dp[i] = max({dp[i], max((i - j)*j, dp[i - j]*j}));
  • dp[i]中取最大值

自己實現過程中遇到哪些困難

整數拆分的遞推公式有點沒理解，如何處理遍歷順序，i=3,那j從什么位置開始。i=3的話，表示要分拆3，因此可以用j(i-j)以及j*dp[i-j]得到最大值。*

不同的二叉搜索樹

96.不同的二叉搜索樹
文章講解：https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
題目鏈接：https://leetcode.cn/problems/unique-binary-search-trees/
視頻講解：https://www.bilibili.com/video/BV1eK411o7QA/

自己看到題目的第一想法

看完代碼隨想錄之后的想法

n=3時
畫出n=3的所有情況，再單獨畫出n=0時，n=1時，n=2的的情況
將整體分為頭節點為1時、頭節點為2時、頭節點為3時的所有情況
頭節點是1時=左子樹0節點情況 * 右子樹2節點數量情況
頭節點是2時=左子樹1節點情況 * 右子樹1節點數量情況
頭節點是3時=左子樹2節點情況 * 右子樹0節點情況
dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0]

// 1. dp[i]的概念就是 n為i的情況下，組成所有二叉搜索樹的情況
// 2. 遞推公式
// 當以j為頭節點時，左節點為j-1個，右節點為i-j個，因為dp[i]是組成所有二叉樹的情況，因此dp[i] += dp[j-1]*dp[i-j]。是累加的情況就是j=1，j=2，j=3…求得的值。
// 3. 初始化值
// 4. 遞推公式 從小到大

自己實現過程中遇到哪些困難

遇到題目時，先畫圖，然后再展開找規律會更好一些。

public int numTrees(int n) {// dp[i]的含義，為i個節點時的二叉搜索樹種數// 遞推公式:// n=3時// 當以1為根節點時，有2種組合，組合即位左邊0的組合數*右邊節點為2個節點時的組合數量。// 當以2為根節點時，有1種組合，左邊1個*右邊1個。// 當以3為根節點時，有2種組合，左邊2個節點的組合鐘數*右邊0個組合種數// 當根節點為j時，左邊有j-1個，右邊有i-j個,dp[j-1]*dp[i-j]// 當給一個整數i時，dp[i] += dp[j-1]*dp[i-j];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];}

今日收獲&學習時長

今天的2道題都是直接看視頻，然后看答案的，看完答案然后自己手寫一遍。還需要多重復刷幾次。
學習時長：2小時