不同路径 - 组合数学
func uniquePaths(m int, n int) int {
res := 1
for x, y := n, 1; y < m; {
res = res * x / y
x++
y++
}
return res
}整数拆分 - 动态规划
func integerBreak(n int) int {
if n < 2 {
panic("input error")
}
// dp[i]: 拆分i的最大乘积
dp := make([]int, n + 1)
dp[2] = 1
for i := 3; i <= n; i++ {
for j := 1; j < i - 1; j++ {
dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
}
}
return dp[n]
}整数拆分 - 贪心
N>4 时，每次拆成 n 个 3，再相乘剩下的数，但是这个结论需要数学证明其合理性！
func integerBreak(n int) int {
if n < 2 {
panic("input error")
}
if n == 2 {
return 1
}
if n == 3 {
return 2
}
if n == 4 {
return 4
}
res := 1
for n > 4 {
res *= 3
n -= 3
}
res *= n
return res
}不同的二叉搜索树 - 动态规划
func numTrees(n int) int {
if n < 1 {
panic("input error")
}
dp := make([]int, n + 1)
dp[0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
dp[i] += dp[j - 1] * dp[i - j]
}
}
return dp[n]
}