代码随想录训练营第41天|343.整数拆分，96.不同的二叉搜索树

343.整数拆分

文章

代码随想录|0343.整数拆分

思路

二刷不难
$$\begin{array}{c}dp[i]=Ma{x}_j(max(j+1,dp[j])\ast (i-j))\end{array}$$

代码

class Solution {public int integerBreak(int n) {int[] dp = new int[n];int i, j;int prefix;for (i = 1; i < n; ++i) {for (j = 0; j < i; ++j) {dp[i] = Math.max(dp[i], Math.max(j + 1, dp[j]) * (i - j));}}// for (i = 0; i < n; ++i) {//     System.out.print(" " + dp[i]);// }return dp[n - 1];}
}

96.不同的二叉搜索树

文章

代码随想录|0096.不同的二叉搜索树

思路

二刷不难
二叉搜索树的数量等于左子树的数量乘右子树的数量
其组合有(0, n - 1), … (n - 1, 0)共n种
$$dp[i]=\sum _{j<i}dp[j]\ast dp[i-1-j]$$

代码

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

总结

二刷就乏善可陈