动态规划专题 1

2020/01/28 Prolems

目录

53. 最大子序和 简单

  • 题目描述

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    Example:

    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

  • 解法

    连续到某个位置的最大值可能是上一位加上这个值和这个值的最大值。

  • 代码

      class Solution {
          public int maxSubArray(int[] nums) {
              if(nums.length==0) return 0;
              int[] dp = new int[nums.length];//因为在动态规划专题,就写复杂些,用动态规划了,其实他只需要关注最新的最大值,所以用个常量保存就够了。dp[i] 表示的是连续到第 i 个位置的最大值(必须含 nums[i])。递推公式 dp[i] = Math.max(dp[i-1]+nums[i],nums[i])
              int max = nums[0];
              dp[0] = nums[0];
              for(int i=1;i<nums.length;i++){
                  dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
                  max = Math.max(max,dp[i]);
              }
              return max;
          }
      }
    

300. 最长上升子序列 中等

  • 题目描述

    给定一个无序的整数数组,找到其中最长上升子序列的长度。

    Example:

    输入: [10,9,2,5,3,7,101,18]
    输出: 4
    解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

  • 解法

    用一个数组保存目前的递增序列,新的数去替换最小的一个比新的数大的数。如果他比最后一个数大,就插入数组。关键是二分法怎么去找。

  • 代码

      class Solution {
          public int lengthOfLIS(int[] nums) {
              if(nums.length==0) return 0;
              int[] dp = new int[nums.length]; //dp是一个有可能的数组,在数组的遍历过程中,只要把最小的大于这个位置的数替换掉就好了,如果没有这个数,则补充在数组后面,因为他比所有数都大。这个数组也一定是个递增的
              dp[0] = nums[0];
              int end = 0;
              for(int num:nums){
                  int index = binarySearch(dp,end,num);
                  dp[index] = num;
                  if(index>end) end = index;
              }
              return end+1;
          }
          public int binarySearch(int[] dp,int end, int num){ // 因为数组长度提前定下来的,所以有个 end
              if(num>dp[end]){
                  return end+1;
              }
              int start = 0;
              while(start<end){
                  int mid = start+(end-start)/2;
                  if(dp[mid]>num){
                      end = mid; //不要写 mid-1,这是最小的比他大的,有可能就是 mid 是最小的比他大的。
                  }else if(dp[mid]<num){
                      start = mid+1;
                  }else{
                      return mid; //如果等于证明不用替换了
                  }
              }
              return start;
          }
      }
    

121. 买卖股票的最佳时机 简单

  • 题目描述

    给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

    如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

    注意你不能在买入股票前卖出股票。

    Example:

    输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

  • 解法

    遍历数组,记录一个当前的最小值,每次减最小值更新最大值。

  • 代码

      class Solution {
          public int maxProfit(int[] prices) {
              int max=0;
              if(prices.length==0) return 0;
              int min = prices[0];
              for(int i=1;i<prices.length;i++){
                  min = Math.min(prices[i],min);
                  max = Math.max(prices[i]-min,max);
              }
              return max;
          }
      }
    

122. 买卖股票的最佳时机 II 简单

  • 题目描述

    给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

    设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

    注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

    Example:

    输入: [7,1,5,3,6,4]
    输出: 7
    解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

  • 解法

    遇到有比前一天多的就立即卖出。其实是求几个波峰波谷的差,这种方式就是把每一段拆成一个个小段累加。

  • 代码

      class Solution {
          public int maxProfit(int[] prices) {
              //遇到下一天多立即卖出
              int sum=0;
              if(prices.length==0) return 0;
              int pre=prices[0];
              for(int i=1;i<prices.length;i++){
                  if(prices[i]>pre) sum+=prices[i]-pre;
                  pre = prices[i];
              }
              return sum;
          }
      }
    

309. 最佳买卖股票时机含冷冻期 中等

  • 题目描述

    给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

    Example:

    输入: [1,2,3,0,2]
    输出: 3
    解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

  • 解法

    这是一个三状态问题。买入后有可能由买入和等待而来,等待只能是由等待或卖出来,卖出只能是由买入来。

  • 代码

      class Solution {
          public int maxProfit(int[] prices) {
              if(prices.length==0) return 0;
              int[] sell = new int[prices.length+1];//最后一次操作是卖出
              int[] buy = new int[prices.length+1];//最后一次操作是买入
              int[] wait = new int[prices.length+1];//最后一次操作是等待
              sell[0] = 0;
              wait[0] = 0;
              buy[0] = -prices[0];
              for(int i=1;i<prices.length;i++){
                  sell[i] = buy[i-1]+prices[i];
                  buy[i] = Math.max(wait[i-1]-prices[i],buy[i-1]); 
                  wait[i] = Math.max(wait[i-1],sell[i-1]);
              }
              return Math.max(sell[prices.length-1],wait[prices.length-1]);
          }
      }
    

198. 打家劫舍 简单

  • 题目描述

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

    给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

    Example:

    输入: [1,2,3,1]
    输出: 4
    解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。

  • 解法

    动态规划,公式为最大值是前一个屋的值或者前两屋的值加当前的值。

  • 代码

      class Solution {
          public int rob(int[] nums) {
              int[] dp = new int[nums.length+1];
              if(nums.length==0) return 0;
              dp[1] = nums[0];
              dp[0] = 0;
              for(int i=2;i<=nums.length;i++){
                  dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
              }
              return dp[nums.length];
          }
      }
    

213. 打家劫舍 II 中等

  • 题目描述

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

    给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

    Example:

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
    给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

  • 解法

    两次动态规划,第一次不要头,第二次不要尾巴,取最大值。

  • 代码

      class Solution {
          public int rob(int[] nums) {
              int[] dp = new int[nums.length+1]; //不加上最后一个
              int[] dp2 = new int[nums.length+1]; //不加第一个
              if(nums.length==0) return 0;
              if(nums.length == 1) return nums[0];
              dp[1] = nums[0];
              dp[0] = 0;
              for(int i=2;i<=nums.length-1;i++){
                  dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
              }
              dp2[2] = nums[1];
              dp2[1] = 0;
              for(int i=3;i<=nums.length;i++){
                  dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i-1]);
              }
              return Math.max(dp[nums.length-1],dp2[nums.length]);
          }
      }
    

96. 不同的二叉搜索树 中等

  • 题目描述

    给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

    Example:

  • 解法

    dp[n] 代表为 n 时有多少种二叉搜索树,这样可以把 1-n 每一个数都当作跟节点,然后左边开始可能是没有节点到 n-1 个节点,此时右边也就是 n-左边-1 个节点。

  • 代码

      class Solution {
          public int numTrees(int n) {
              int[] dp = new int[n+1]; // 为 n 时有多少种二叉树可能。
              dp[0] = 1;
              for(int i=1;i<=n;i++){
                  for(int j=0;j<i;j++){ // 任意一个点都能做根,左边是 1 的话,右边就是 i-1-左边
                      dp[i]+=dp[j]*dp[i-j-1];
                  }
              }
              return dp[n];
          }
      }
    

120. 三角形最小路径和 中等

  • 题目描述

    给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

    Example:

    给定三角形:

      [
          [2],
         [3,4],
        [6,5,7],
       [4,1,8,3]
      ]
    

    自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

  • 解法

    最后一行的元素数量和总列数相同,所有的最小值必须经过顶部的头的值。可以设 dp[i] 表示到当前行的第 i 个元素的最小值。所以 dp[i] = 此列第 i 个位置的值 + Math.min(dp[i],dp[i+1])

  • 代码

      class Solution {
          public int minimumTotal(List<List<Integer>> triangle) {
              int size = triangle.size();
              List<Integer> finalRow = triangle.get(size-1);
              //最后一行列数数量相等,最后肯定要有顶端的点。所以可以设 dp[i] 为到达当前行第 i 个的最小值
              int[] dp = new int[finalRow.size()];
              int min = Integer.MAX_VALUE;
              for(int i=0;i<finalRow.size();i++){
                  dp[i] = finalRow.get(i);
              }
              for(int i=triangle.size()-2;i>=0;i--){
                  List<Integer> thisRow = triangle.get(i);
                  for(int j=0;j<thisRow.size();j++){
                      dp[j] = thisRow.get(j)+Math.min(dp[j],dp[j+1]);
                  }
              }
              return dp[0];
          }
      }
    

63. 不同路径 II 中等

  • 题目描述

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

    现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

    Example:

  • 解法

    每一个格等于他左边的格加上他上边的格。当格子有障碍物时,设为 0。

  • 代码

      class Solution {
          public int uniquePathsWithObstacles(int[][] obstacleGrid) {
              if(obstacleGrid.length == 0) return 0;
              if(obstacleGrid[0][0] == 1) return 0;
              int[] dp = new int[obstacleGrid[0].length];
              dp[0] = 1;
              for(int i=1;i<obstacleGrid[0].length;i++){
                  if(obstacleGrid[0][i]==0 && dp[i-1]==1) dp[i] = 1;
              }
              for(int i=1;i<obstacleGrid.length;i++){
                  for(int j=0;j<obstacleGrid[0].length;j++){
                      if(obstacleGrid[i][j]==1){
                          dp[j] = 0;
                          continue;
                      }
                      if(j==0){
                          if(dp[j]==1)
                          dp[j] = 1;
                      }else{
                          dp[j] = dp[j-1]+dp[j];
                      }
                  }
              }
              return dp[obstacleGrid[0].length-1];
          }
      }
    

338. 比特位计数 中等

  • 题目描述

    给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

    Example:

    输入: 5
    输出: [0,1,1,2,1,2]

  • 解法

    任何一个数 n 和 n-1 的 & 结果都是消掉尾数最后一个 1。

    任何一个数的 1 的数量都是比他 /2 的结果多上 1 再加上尾数是不是 1。

  • 代码

      class Solution {
          public int[] countBits(int num) {
              // i&(i-1) 可以把最后一个 1 消掉,利用这个性质可以求出数里有多少 1
              int[] dp = new int[num+1];
              // 任何一个数的一的数量,都比他除以 2 的 1 数多 1 + 尾数是不是 1
              for(int i=0;i<=num;i++){
                  dp[i] = dp[i>>1]+(i&1);
              }
              return dp;
          }
      }
    

322. 零钱兑换 中等

  • 题目描述

    给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

    Example:

    输入: coins = [1, 2, 5], amount = 11
    输出: 3
    解释: 11 = 5 + 5 + 1

  • 解法

    动态规划,遍历所有的硬币,抛弃一个硬币 +1 也就是新值。

  • 代码

      class Solution {
          public int coinChange(int[] coins, int amount) {
              int[] dp = new int[amount+1];
              for(int i=1;i<=amount;i++){
                  dp[i] = Integer.MAX_VALUE-1;
                  for(int j=0;j<coins.length;j++){
                      if(i-coins[j]>=0)
                      dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                  }
              }
              return dp[amount] == Integer.MAX_VALUE-1?-1:dp[amount];
          }
      }
    

221. 最大正方形 中等

  • 题目描述

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    Example:

  • 解法

    动态规划,dp[i][j]表示以i,j为右下角时能组成的最大正方形边长,既然能组成正方形,也就是保证左边点,上边点以及斜上边点为右下角能组成正方形的最小值+1(因为只要这三点有一个组成中有问题,这正方形就组不起来)

  • 代码

      class Solution {
          //动态规划,dp[i][j]表示以i,j为右下角时能组成的最大正方形边长,既然能组成正方形,也就是保证左边点,上边点以及斜上边点为右下角能组成正方形的最小值+1(因为只要这三点有一个组成中有问题,这正方形就组不起来)
          public int maximalSquare(char[][] matrix) {
              if(matrix.length==0) return 0;
              int[][] dp = new int[matrix.length][matrix[0].length];
              int max = 0;
              for(int i=0;i<matrix.length;i++){
                  for(int j=0;j<matrix[0].length;j++){
                      if(matrix[i][j]!='1'){
                          dp[i][j] = 0;
                          continue;
                      }
                      if(i==0||j==0){
                          dp[i][j] = 1;
                      }else{
                          dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                      }
                      max = Math.max(max,dp[i][j]);
                  }
              }
              return max*max;
          }
      }
    

91. 解码方法 中等

  • 题目描述

    一条包含字母 A-Z 的消息通过以下方式进行了编码。给定一个只包含数字的非空字符串,请计算解码方法的总数。

    Example:

    输入: “226”
    输出: 3
    解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

  • 解法

    动态规划,如果当前位和前一位不能组成 26 以下且不是 0。那此时就是 dp[i-1],如果能组成 26 以下,就是 dp[i-2]+dp[i-1]。否则当前位是 0,他什么都不是。

  • 代码

      class Solution {
          public int numDecodings(String s) {
              int[] dp = new int[s.length()+1];
              dp[0] = 1;
              if(s.charAt(0)=='0') return 0;
              dp[1] = 1;
              char[] cs = s.toCharArray();
              for(int i=2;i<=cs.length;i++){
                  int wordIndex = i-1;
                  int current = 0;
                  int last = 0;
                  if(cs[wordIndex-1]=='1' || (cs[wordIndex]<='6' && cs[wordIndex-1]=='2')){
                      last = dp[i-2];
                  }
                  if(cs[wordIndex] != '0'){
                      current = dp[i-1];
                  }
                  dp[i] = last+current;
              }
              return dp[s.length()];
          }
      }
    

91. 解码方法 中等

  • 题目描述

    一条包含字母 A-Z 的消息通过以下方式进行了编码。给定一个只包含数字的非空字符串,请计算解码方法的总数。

    Example:

    输入: “226”
    输出: 3
    解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

  • 解法

    动态规划,如果当前位和前一位不能组成 26 以下且不是 0。那此时就是 dp[i-1],如果能组成 26 以下,就是 dp[i-2]+dp[i-1]。否则当前位是 0,他什么都不是。

  • 代码

      class Solution {
          public int numDecodings(String s) {
              int[] dp = new int[s.length()+1];
              dp[0] = 1;
              if(s.charAt(0)=='0') return 0;
              dp[1] = 1;
              char[] cs = s.toCharArray();
              for(int i=2;i<=cs.length;i++){
                  int wordIndex = i-1;
                  int current = 0;
                  int last = 0;
                  if(cs[wordIndex-1]=='1' || (cs[wordIndex]<='6' && cs[wordIndex-1]=='2')){
                      last = dp[i-2];
                  }
                  if(cs[wordIndex] != '0'){
                      current = dp[i-1];
                  }
                  dp[i] = last+current;
              }
              return dp[s.length()];
          }
      }
    

264. 丑数 II 中等

  • 题目描述

    编写一个程序,找出第 n 个丑数。

    丑数就是只包含质因数 2, 3, 5 的正整数。

    Example:

    输入: n = 10
    输出: 12
    解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

  • 解法

    动态规划,丑数每一个数都是之前的某个数乘以 2 3 5 得来的,所以记录下当前 2 3 5 所乘到的顺序,每次乘以 2 3 5 找出最小的一个,就是下一个数。

  • 代码

      class Solution {
          public int nthUglyNumber(int n) {
              int i2=0,i3=0,i5 = 0;
              int res = 1;
              int dp[] = new int[n];
              dp[0] = 1;
              for(int i=1;i<=n-1;i++){
                  int temp2 = dp[i2]*2;
                  int temp3 = dp[i3]*3;
                  int temp5 = dp[i5]*5;
                  res = Math.min(temp2,Math.min(temp3,temp5));
                  dp[i] = res; 
                  if(temp2==res){
                      i2++;
                  }
                  if(temp3==res){ //绝对不能用 else if 有相同值问题
                      i3++;
                  }
                  if(temp5==res){
                      i5++;
                  }
              }
              return dp[n-1];
          }
      }
    

Search

    Table of Contents