DP-Easy

Abstract： 更新部分Easy难度 DP相关题解

70. Climbing Stairs

解法一：DP

• 基本情况：一层楼梯有一种方法，两层楼梯两种方法，因此dp[0]=1,dp[1]=2
• 转移方程：对于大于等于2的层数，dp[n-1]=dp[n-2]+dp[n-3]，即为一般解

class Solution {
    public int climbStairs(int n) {
        if(n<=1){return 1;}
        if(n==2){return 2;}
        int[] dp=new int[n];
        dp[0]=1;
        dp[1]=2;
        for(int i=2;i<n;i++){dp[i]=dp[i-1]+dp[i-2];}
        return dp[n-1];
    }
}

121. Best Time to Buy and Sell Stock

解法一：线性扫描

线性扫描，考虑到不能只求最大值和最小值，但是记录Index也是无用功

不妨只更新最小值，那么计算利润的值就必定是在最小值之后，那就只需无脑更新最大利润就行了

时间复杂度：$ O(N) $

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit=0,minPrice=Integer.MAX_VALUE; //只需要最大利润和最小值
        for(int i=0;i<prices.length;i++){
            minPrice=Math.min(prices[i],minPrice); 
            maxProfit=Math.max(maxProfit,prices[i]-minPrice);
        }
        return maxProfit;
    }
}

解法二：DP

//下次写(?)

198. House Robber

解法一：DP

• 特殊情况：可抢劫的房子不到三家，即0,1,2

• 基本情况：第一家的价值是其自身，第二家的价值是第一家和第二家价值的最大值，即

  dp[0]=nums[0];
  dp[1]=Math.max(nums[0],nums[1]);
  

• 转移方程：由基本情况可以推出，第n家的价值

  dp[n]=Math.max(
      dp[n-2]+nums[n],
  	dp[n-1]
  );
  

• 结果：不是最后一家就是倒数第二家，取最大值即可

class Solution {
    public int rob(int[] nums) {
        //三种特殊情况,不考虑会越界
        if(nums.length==0 || nums==null){return 0;}
        if(nums.length==1){return nums[0];}
        if(nums.length==2){return Math.max(nums[0],nums[1]);}
        int[] dp=new int[nums.length];
        //两种基本情况
        dp[0]=nums[0];
        dp[1]=Math.max(dp[0],nums[1]);
        //状态转移
        for(int i=2;i<nums.length;i++){dp[i]=Math.max((dp[i-2]+nums[i]),dp[i-1]);}
        //最后两家的价值取最大值即可
        return Math.max(dp[nums.length-1],dp[nums.length-2]);
    }
}

303. Range Sum Query - Immutable

解法一：缓存

由于会大量调用，所以如果每次都遍历一次来计算会很慢，所以这里需要加入缓存

nums传入初始化时，就把到n为止的sum计算出来，结果返回两个边界的差值就行了

class NumArray {

    private int[] sum;

    public NumArray(int[] nums) {
        sum=new int[nums.length+1];
        for(int i=0;i<nums.length;i++){
            sum[i+1]=nums[i]+sum[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return sum[j+1]-sum[i];
        //注意这里是j+1 和 i ，因为如果是i+1的话，会把nums[i]也算进去，那得到的和就没有nums[i]了
    }
}

62. Unique Paths（Medium？Easy？）

解法一：DP

• 基本情况：每个格子对应的解数应为

• 转移方程：每个格子对应的解数应为 左方格子的解数+上方格子的解数，因此

  dp[i][j]=dp[i-1][j]+dp[i][j-1];
  

• 边界问题：由于边界上的格子上方或左方没有格子，直接计算会导致越界，因此长宽各扩展一格val=0的格子来作辅助

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1]; //长宽都+1，自动初始化为0作为辅助
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=(i==1&&j==1)?1:dp[i-1][j]+dp[i][j-1];
                //dp[1][1]为1，其他则由其按转移方程推得
            }
        }
        return dp[m][n];//右下角即为结果
    }
}