刷题之动态规划-多状态

前言

大家好,我是jiantaoyab,开始刷动态规划的多状态类型相关的题目

动态规划5个步骤

  1. 状态表示 :dp数组中每一个下标对应值的含义是什么>dp[i]表示什么
  2. 状态转移方程: dp[i] 等于什么
  3. 1 和 2 是动态规划的核心步骤,第三步是初始化,保证填表的时候不越界
  4. 填表顺序:为了保证填写当前状态的时候,所需要的状态已经计算过
  5. 返回值

按摩师

image-20240330082648430

题目分析

  1. 初始化:f[i] = nums[0], g[i] = 0;
  2. 返回值:返回max(f[n - 1], g[n - 1]);

image-20240330085657931

代码

class Solution {
public:
    int massage(vector<int>& nums) {
      if(nums.size() == 0) return 0;
      int n = nums.size();
      vector<int> f(n), g(n);
      //初始化
      f[0] = nums[0];

      for(int i = 1; i < n; i++)
      {
        //选
        f[i] = g[i - 1] + nums[i];
        //不选
        g[i] = max(f[i - 1], g[i - 1]);

      }
      return max(f[n - 1], g[n - 1]);
    }
};

打家劫舍II

image-20240330091145743

题目分析

image-20240330093947853

代码

class Solution {
public:
    int rob1(vector<int>& nums, int l, int r)
    {
      if(l > r) return 0;
      int n = nums.size();
      vector<int> f(n), g(n);
      //初始化
       f[l] = nums[l];
        for(int i = l + 1; i <= r; i++)
        {
          f[i] = g[i - 1] + nums[i];
          g[i] = max(g[i - 1], f[i - 1]);
        }
        return max(f[r], g[r]);
    }
    int rob(vector<int>& nums) {
      if(nums.size() == 0) return 0;
      int n = nums.size();
      //第一个位置选
      int x = rob1(nums, 2, n - 2) + nums[0];
      //第1个位置不选
      int y = rob1(nums, 1, n - 1);
      return max(x, y);          
    }
};

删除并获得点数

image-20240330100540378

题目分析

image-20240330103035842

f [i] : 到达 i 位置 nums[i] 选上,此时的最大点数

g [i] : 到达 i 位置 nums[i] 不选,此时的最大点数

初始化:f[0] = arr[0];

返回值:max(f[n - 1], g[n -1]);

代码

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
      const int N = 100001;
      //预处理
      sort(nums.begin(), nums.end());
      int arr[N] = {0};
      for(auto x : nums) arr[x] += x;
     
      vector<int> f(N), g(N);
      for(int i = 1; i < N; i++)
      {
        f[i] = g[i - 1] + arr[i];
        g[i] = max(g[i - 1], f[i - 1]);
      }
      return max(f[N - 1], g[N - 1]);
    }
};

粉刷房子

image-20240331083843484

题目分析

image-20240331085932699

**初始化:**新增加一个节点初始化为0

**填表顺序:**从左到右,3个表同时填

**返回值:**min(dp[n] [0],dp[n] [1],dp[n] [2]);

代码

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int>(3));
        for(int i = 1; i <= n; i++)
        {
          dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
          dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
          dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
        }

        return min(dp[n][0], min(dp[n][1], dp[n][2]));
    }
};

买卖股票的最佳时机含冷冻期

image-20240331092541014

题目分析

image-20240331101028734

**初始化:**dp[0] [0] = -prices[0]; dp[1] [0] = dp[2] [0] = 0;

返回值: max(dp[n - 1] [1], dp[n - 1] [2]);

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
      int n =  prices.size();
      vector<vector<int>> dp(n, vector<int>(3));
      //初始化
      dp[0][0] = -prices[0];
      for(int i = 1; i < n; i++)
      {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
        dp[i][1] = dp[i - 1][0] + prices[i];
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][2] );
      }
      return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

买卖股票的最佳时机含手续费

image-20240331101206123

题目分析

和上一道题目是类似的。

image-20240331105029901

代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
       int n =  prices.size();
      vector<vector<int>> dp(n, vector<int>(2));
      //初始化
      dp[0][0] = -prices[0] ;
      for(int i = 1; i < n; i++)
      {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i] );
        dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i] - fee);
      }
      return dp[n - 1][1];
    }
    
};

买卖股票的最佳时机 III

image-20240331105341935

题目分析

这道题目的最大不同就是最多能完成2笔交易,就是可以0笔1笔2笔。

image-20240331201435009

一般初始化负无穷的时候可以初始化为-0x3f3f3f3f。

**返回值:**返回g表最后一行的最大值

代码

class Solution {
   const int INF = 0x3f3f3f3f;
public:
    int maxProfit(vector<int>& prices) {
      int n = prices.size();
      vector<vector<int>> f(n, vector<int>(3, -INF));
      vector<vector<int>> g(n, vector<int>(3, -INF));
      //初始化
      f[0][0] = -prices[0], g[0][0] = 0;
      for(int i = 1; i < n; i++)
      {
        for(int j = 0; j < 3; j++)
        {
          f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
          g[i][j] = g[i - 1][j];
          if(j - 1 >= 0) 
            g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
        }
      }

      int ret = 0;
      for(int j = 0; j < 3; j++)
         ret = max(ret, g[n - 1][j]);
      return ret;
    }
};

买卖股票的最佳时机 IV

image-20240331163643702

代码

和III的区别就是最大交易次数变成k,其他没什么区别。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
      const int INF = 0x3f3f3f3f;
      int n = prices.size();
      k = min(k, n / 2); //k执行一半就行
      vector<vector<int>> f(n, vector<int>(k + 1, -INF));
      vector<vector<int>> g(n, vector<int>(k + 1, -INF));
      //初始化
      f[0][0] = -prices[0],  g[0][0] = 0;
      for(int i = 1; i < n; i++)
      {
        for(int j = 0; j <= k; j++)
        {
          f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
          g[i][j] = g[i - 1][j];
          if(j - 1 >= 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
        }
      }

      int ret = 0;
      for(int j = 0; j <= k; j++)
        ret = max(ret, g[n - 1][j]);

      return ret;

    }
};

相关推荐

  1. 【算法专题】动态规划简单状态 dp 问题

    2024-04-02 06:46:05       21 阅读
  2. 力扣区间动态规划类题目

    2024-04-02 06:46:05       12 阅读
  3. LeetCode笔记动态规划(二)

    2024-04-02 06:46:05       7 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-04-02 06:46:05       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-02 06:46:05       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-02 06:46:05       9 阅读
  4. 高级IO——React服务器简单实现

    2024-04-02 06:46:05       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-02 06:46:05       7 阅读
  6. go第三方库go.uber.org介绍

    2024-04-02 06:46:05       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-02 06:46:05       10 阅读

热门阅读

  1. 【NoSQL数据库】【redis】redis基础知识整理

    2024-04-02 06:46:05       3 阅读
  2. wpf Menu

    2024-04-02 06:46:05       9 阅读
  3. 1049. 最后一块石头的重量 II(力扣LeetCode)

    2024-04-02 06:46:05       4 阅读
  4. 2022-04-10作业

    2024-04-02 06:46:05       4 阅读
  5. veu视图刷新Vue.$set和Vue.$forceUpdate的区别

    2024-04-02 06:46:05       3 阅读
  6. 深入理解VUE的keep-alive

    2024-04-02 06:46:05       2 阅读