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>