LeetCode —— 动态规划

lalala / 2023-05-14 / 原文

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

f(x) = f(x-1) + f(x-2)

f(0)=1 f(1)=1 f(2)=2 ---> f(3)=3 ---> f(4)=5

设一个存放三个整数的数组，分别保存 f(x-2) f(x-1) f(x) 。每次来了新的 f(x) ，前两个向前移动，然后把它放到数组末尾。

 public int climbStairs(int n) {
        // 分别存放 f(x-2) f(x-1) f(x)
        int[] arr = new int[]{0,1,2};
        if (n<=2) {
            return arr[n];
        }
        for (int i=3;i<=n;i++) {
            //  f(x) = f(x-1) + f(x-2)
            int fx = arr[2] + arr[1];
            // fx 放在末尾，数组往前移
            arr[0] = arr[1];
            arr[1] = arr[2];
            arr[2] = fx;
        }
        return arr[2];
    }

53. 最大子数组和

　dp[i] 代表表示以 nums[i] 结尾的连续子数组的最大和。

　要么把 nums[i] 附加到前一个连续最大和的后面，要么从 nums[i] 重新开始

dp[i]=max{nums[i],dp[i−1]+nums[i]}

class Solution {
    public int maxSubArray(int[] nums) {
        int result = nums[0];
        int dp[] = new int[nums.length];
        dp[0] =  nums[0];
        for(int i=1;i<nums.length;i++){
           //递推公式
           dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
           //result用来记dp数组里的最大数值
           if(dp[i]>result)
                result = dp[i];
        }
        return result;
    }
}

96. 不同的二叉搜索树

如果整数1 ~ n中的 k 作为根节点值，则 1 ~ k-1 会去构建左子树，k+1 ~ n 会去构建右子树。
左子树出来的形态有a 种，右子树出来的形态有 b 种，则整个树的形态有 a∗b 种。

题解参考： https://leetcode.cn/problems/unique-binary-search-trees/solution/shou-hua-tu-jie-san-chong-xie-fa-dp-di-gui-ji-yi-h/

class Solution {

    public int numTrees(int n) {
        // 最后要返回 dp[n]
        int dp[] = new int[n+1];

        // dp[0] 代表用 0 个数去构建左子二叉搜索树，dp[n-1] 代表用 n-1 个数（除掉根节点）去构建右子二叉搜索树
        // dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2] + dp[2]*dp[n-3] + ..... + dp[n-2]*dp[0] + ... dp[n-1]*dp[0]
        // 一共有 i 个数，左子树用 j 个，右子树用 i-j-1 个  dp[i] = dp[j]dp[i-j-1]之和 0<=j<=i-1（左子树可以用0个到i-1个（除根节点））

        // 空树，只有一种
        dp[0] = 1;
        // 一个数字的，只有一种
        dp[1] = 1;

        // dp[0] 和 dp[1] 已知，所以从 dp[2] 开始
        for (int i=2;i<=n;i++) {
            // 左子树可以用0个到i-1个（除根节点）
            for (int j=0;j<=i-1;j++) {
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }

}