Unique Binary Search Trees
给定一个数组，含有 n 个数的数组（连续的 1 - n），利用这N个数组建一个 二叉树，求能够构建二叉树的数量,例如 n = 3 能够构建的二叉树数量为 5
- 思路：
- DP[0] = 1,
- DP[1] = 1;
- DP[2] = DP[1] x DP[0] + DP[0] x DP[1] = 2; DP[3] = DP[2] x DP[0] + DP[0] x DP[2] + DP[1] x D[1] = 5
public class Solution {
public int numTrees(int n) {
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++) //表示在每个小于 i 的值在做root节点时，其值
dp[i] += dp[j - 1] * dp[i - j];
return dp[n];
}
}
Maximum Product Subarray
给定一个数组，有正的也有负的，求一个连续的最大乘积区间， 例如给定 [2,3,-2,4],最大区间就是 [2,3],为6.求最大的这个值
- 思路：在区间上的每个节点记录两个值，一个最大值和一个最小值。因为假设在 index i 上当第一次遇到一个负值时候，那么 i-1的最大值就成了最小值，但是我们要记录它，如果再碰到一个负值，可能它就变成最大值了。思路就是这样
func maxProduct(nums []int) int {
if (len(nums) < 1){
return 0
}
max := nums[0]
min := nums[0]
result := max
for index := 1;index < len(nums); index ++{
num := nums[index]
//作为临时记录，方式变更
temp := max
//最大值，和最小值都记录下来，因为接下来很有可能翻转
max = int(math.Max(math.Max(max * num,min * num),num))
min = int(math.Min(math.Min(min * num,temp * num),num)) //最小值
if (max > result){
result = max
}
}
return result
}
最大连续区间
- 思路 ： DP[i] = math.max(DP[i - 1] + array[i],array[i])
01背包问题
- <p font = 5> 思路： DP[i][j] 是当前的总利润 。，就是每次在拿起一个物品的时候，判断一下是dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]）</p>
