已解答 中等
相关标签
相关企业提示
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
func integerBreak(n int) int { //dp[i] 的含义 该正整数的最大乘积 // 递推公式 dp[5] = max(1,dp[4],2*dp[3],3*dp[2], 1*4,2*3) // 初始化 dp[2] = 1, dp[3] = max(1*2,1*dp[2]) dp[4] = max(1*3,2*2,1*dp[3],2*dp[2]) // 遍历，从3遍历到n // 输出 var dp []int dp = make([]int, n+1) dp[2] = 1 for i := 3; i < n+1; i++ { var maxRes int for j := 1; j <= i/2; j++ { if j*(i-j) > maxRes { maxRes = j * (i - j) } cur := j * dp[i-j] if cur > maxRes { maxRes = cur } } dp[i] = maxRes } return dp[n] }
已解答 中等
相关标签
相关企业给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
func numTrees(n int) int { //dp[i] , 满足题意的二叉搜索树种数 //递推公式， dp[4] = dp[3]*dp[0] + dp[2]*dp[1] + dp[1]*dp[2] + dp[0]*dp[3] //初始化 dp[0] = 1 dp[1] = 1 // dp[0->n-1] * dp[n-1->0] //输出dp结果 dp := make([]int, n+1) dp[0], dp[1] = 1, 1 fori := 2; i < n+1; i++ { varansint forj := 0; j < i; j++ { ans += dp[j] * dp[i-j-1] } dp[i] = ans } return dp[n] } 标签：示例,int,随想录,二叉,搜索,maxRes,343,dp,96 From： https://www.cnblogs.com/suxinmian/p/18061067