LeetCode---动态规划系列

目录

• #96 不同的二叉搜索树
• #375 猜数字大小 II

#96 不同的二叉搜索树

https://leetcode-cn.com/problems/unique-binary-search-trees/

总数 = 分别以每一个节点做根节点的种数相加。
F(n) = S(1) + S(2) + ... + S(n)。
S(i) = F(i的左子树) * F(i的右子数)。

        public int NumTrees(int n)
        {
            if (n<=0)
                return 0;

            int[] treeNum = new int[n + 1];
            treeNum[0] = 1;
            treeNum[1] = 1;

            //F(n) = S(1) + S(2) + ... + S(n)。
            //S(i) = F(i的左子树) * F(i的右子数)。
            for (int i = 2; i <= n; i++)
            {
                for (int j = 1; j <= i; j++)
                {
                    treeNum[i] += treeNum[i - j] * treeNum[j - 1];
                }
            }

            return treeNum[n];
        }

#375 猜数字大小 II

https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/

        public static int GetMoneyAmount(int n)
        {
            int[,] dp = new int[n + 1,n + 1];

            if (n==1)
                return 0;

            //初始化除了斜线上的值为0
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= n; j++)
                {
                    if (i != j)
                        dp[i, j] = int.MaxValue;
                }
            }

            for (int i = 2; i <= n; i++)
            {
                for (int j = i-1; j >=1; j--)
                {
                    for (int k = j+1; k <= i-1; k++)
                    {
                        dp[j, i] = Math.Min(dp[j, i], k + Math.Max(dp[j, k - 1], dp[k + 1, i]));
                    }
                    dp[j, i] = Math.Min(dp[j, i], j + dp[j + 1, i]);
                    dp[j, i] = Math.Min(dp[j, i], i + dp[j, i-1]);
                }
            }

            return dp[1,n];
        }