代码随想录训练营第41天|343.整数拆分，96.不同的二叉搜索树
代码随想录训练营第41天|343.整数拆分，96.不同的二叉搜索树
- 343.整数拆分
- 文章
- 思路
- 代码
- 96.不同的二叉搜索树
- 文章
- 思路
- 代码
- 总结
343.整数拆分
文章
代码随想录|0343.整数拆分
思路
二刷不难
d p [ i ] = M a x j ( m a x ( j + 1 , d p [ j ] ) ∗ ( i − j ) ) \begin{equation} dp[i]=Max_j(max(j + 1, dp[j]) * (i - j)) \end{equation} dp[i]=Maxj(max(j+1,dp[j])∗(i−j))
代码
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种
d p [ i ] = ∑ j < i d p [ j ] ∗ d p [ i − 1 − j ] dp[i] = \sum_{j<i} dp[j]*dp[i - 1 - j] dp[i]=j<i∑dp[j]∗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];}
}
总结
二刷就乏善可陈