leetcode刷题(4): 动态规划

@BangBang

924人浏览 · 2024-05-04 15:08:51

@BangBang · 2024-05-04 15:08:51 发布

42. 接雨水

题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例:

在这里插入图片描述

解题思路

使用动态规划(DP)方法求解
当前位置接水体积计算公式: $min(Left_{max},Right_{max})-CurrHeight$
从左到右遍历数组得到每个位置左边柱子高度的最大值 $Left_{max}$ ；从右到左遍历数组得到每个位置所有右边柱子高度的最大值 $Right_{max}$
根据得到的每个位置的 $Left_{max}$ 和 $Right_{max}$ ，利用积水量计算公式

如上图黄色标识位置所示：min(leftmax,rightmax)=min(1,3)为1，此时柱子高度为1。所以盛水体积为1。下一个位置 min(leftmax,rightmax)=min(1,3)=1, 此时柱子高度height为0, 根据:min(leftmax,rightmax)-height =1, 此处盛水体积为1

c++ 实现

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

64. 最小路径和

题目: 给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

在这里插入图片描述

解题思路

假设dp[i][j]为从起点(左上角点)到grid[i][j]的路径的总数字之和
由于每次只能向下或者向右移动，那么dp[i][j]就有:

// 从前一步dp[i-1][j]向下移动grid[i,j]
dp[i][j]=dp[i-1][j] +grid[i][j]
// 或者
//从前一步dp[i][j-1]向右移动grid[i,j]
dp[i][j] = dp[i][j-1]+grid[i][j]

此时，每个格子最小取值只能在该格子左端的格子和上端的格子的最小值中取其一公式表示为:dp[i][j] = min(dp[i-1][j] +grid[i][j],dp[i][j-1]+grid[i][j]),根据该公式即可求解

c++ 实现

class Solution {
public:
    int dp[300][300];
    int minPathSum(vector<vector<int>>& grid) {
        memset(dp,0x3f,sizeof(dp));
        dp[0][0] = grid[0][0];
        int n = grid.size();
        int m = grid[0].size();
        for(int i = 0; i < grid.size();i++){
            for(int j = 0; j < grid[0].size();j++){
                if(j-1 >=0)
                    dp[i][j] = min(dp[i][j],dp[i][j-1]+grid[i][j]);   
                if(i-1>=0)
                    dp[i][j] = min(dp[i][j],dp[i-1][j]+grid[i][j]);
            }
        }

        return dp[n-1][m-1];
    }
};

由于 1=<m,n<=200, 因此初始化dp[300][300],空间是足够的
初始化dp，由于我们求的是最小值，所以初始化dp为最大值;注意一定要memset(dp,0x3f,sizeof(dp));使用INT_MAX以及1000来初始化结果都出错，可能是会造成Int越界把
根据公式dp[i][j] = min(dp[i-1][j] +grid[i][j],dp[i][j-1]+grid[i][j]),所以需要对比向右向下两种情况，取其中最小的。其中当i=0, 此时dp[i][j]，只能由dp[i][j-1]向右移动一步；同理当j=0, 此时dp[i][j], 只能由dp[i-1][j]向下移动一步。所以有:

  for(int i = 0; i < grid.size();i++){
            for(int j = 0; j < grid[0].size();j++){
                if(j-1 >=0)
                    dp[i][j] = min(dp[i][j],dp[i][j-1]+grid[i][j]);   
                if(i-1>=0)
                    dp[i][j] = min(dp[i][j],dp[i-1][j]+grid[i][j]);
            }
        }

最后返回从左上角到右下角的值: dp[n-1][m-1]

62 不同路径

题目:一个机器人位于一个m x n网格的左上角（起始点在下图中标记为“Start”）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例:
在这里插入图片描述

解题思路

由于机器人只能向下和向右走，因此达到指定格子的最后一步，要么是向下要么是向右到达。
假设dp[i][j] 表示第i行j列能达到的方案数目，就有 dp[i][j] = dp[i-1][j] + dp[i][j-1](), 即到达指定格子的路径数目就等于到达相邻的上方和左方的两个格子的路径数目之和。

在这里插入图片描述

c++ 实现

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[110][110];
        memset(dp,0,sizeof(dp));
        dp[0][0] =1;
        for (int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i>0)
                    dp[i][j] += dp[i-1][j];
                if (j>0)
                    dp[i][j] += dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
};

对于 i>0且j>0 ,此时到达第i行j列能的方案数目为： dp[i][j] = dp[i-1][j] +dp[i][j-1]。
但对于i =0这种情况，只能通过向右移动到达第i行j列，此时该方案数目为: dp[i][j] = dp[i][j-1]; 同理对于j=0时，只能通过向下移动到达第i行j列，此时该方案数目为：dp[i][j] = dp[i-1][j];因此代码有如下代码:

 for (int i=0;i<m;i++)
	{
	       for(int j=0;j<n;j++)
	       {
	           if(i>0)
	               dp[i][j] += dp[i-1][j];
	           if (j>0)
	               dp[i][j] += dp[i][j-1];
	       }
	   }

5 最长回文子串

题目给你一个字符串 s，找到 s 中最长的回文子串。(如果相同长度的最长回文子串，返回任意一个都可以)。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例
在这里插入图片描述

解题思路

本题有两种解法：(1) 利用双指针 (2) 使用动态规划；其中双指针参考博文，本文重点介绍使用动态规划来求解
使用dp[i][j]表示字符串索引i 到索引j, 是否是回文串。它取决于2个条件:
- (1) 索引i 和索引j 位置字符是否相等: s[i] == s[j]
- (2) 同时还需要判断dp[i+1][j-1] =1，其中dp[i+1][j-1]=1 表示字符串索引i+1到j-1范围内是回文字符串

c++ 实现

class Solution {
public:
   

    // dp[i][j]表示字符串i到j是否是回文字符串
    // dp[i][j] =1, 取决于 dp[i+1][j-1] =1 && s[i]==s[j]
    vector<vector<int>> dp;

    string longestPalindrome(string s)
    {
        s.insert(s.begin(),'#');
        dp = vector<vector<int>>(s.size()+10,vector<int>(s.size()+10));

        int maxLen =1; int maxi =1; int maxj=1;

        // 单个字母和连续两个相同的字母肯定是回文
        for(int i=1;i<s.size();i++)
        {
            dp[i][i] =1;
            if(s[i-1] == s[i])
            {
                dp[i-1][i] =1;
                if(maxLen<2) {maxLen =2; maxi =i-1;maxj=i;}
            }
        }

        for(int i=1;i<s.size();i++)
        {
            for(int j=1;j<i;j++)  // j<i ,因为这里判断从j到i是否是回文字符串
            {
                if(s[i]==s[j] && dp[j+1][i-1] ==1)
                {
                    dp[j][i] =1;
                    if (maxLen <i-j+1) {maxLen =i-j+1;maxi=j;maxj=i;}
                }
            }
        }

        string ans = s.substr(maxi,maxj-maxi+1);
        return ans;
    }

};

初始化二维数组dp,maxLen和maxi以及maxj

//初始化一个空间稍大一点的dp
dp = vector<vector<int>>(s.size()+10,vector<int>(s.size()+10));
int maxLen =1; int maxi =1; int maxj=1;

首先单个字母和连续两个相同的字母肯定是回文

for(int i=1;i<s.size();i++)
{
      dp[i][i] =1;
      if(s[i-1] == s[i])
      {
          dp[i-1][i] =1;
          if(maxLen<2) {maxLen =2; maxi =i-1;maxj=i;}
      }
  }

如果满足条件: s[i]==s[j] && dp[j+1][i-1] ==1, 那么dp[j][i]肯定也是回文，并更新maxlen和maxi以及maxj
返回maxi到maxj范围截取的最大回文字符创

221 最大正方形

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

示例:
在这里插入图片描述

解题思路

使用动态规划求解，设dp[i][j] 表示以(i,j)位置为右下角，能构成的最大正方形

构成n边正方形，则底边和对角线都有连续n个1，从右下角往右上角也满足连续n个1
遍历二维矩阵，统计每个位置，从左到该位置（底边），连续为1的个数, 记为lr[i][j]
遍历二维矩阵，统计每个位置，从上往下到该位置，连续为1的个数, 记为ud[i][j]
可以发现，满足dp[i][j] = min(min(lr[i][j],ud[i][j])+1, dp[i-1][j-1]), 其中min(lr[i][j],ud[i][j]),为从左往右到该该位置（底边）和从上往下到该位置(上边)最小值， dp[i-1][j-1]以(i-1,j-1)位置为右下角，能构成的最大正方形数量

c++ 实现

class Solution {
public:
	int ans = 0;
	int lr[310][310];           // 记录每个元素左边到自己的连续1的长度
	int ud[310][310];           // 记录每个元素上边到自己的联系1的长度
	void Check(const vector<vector<char>>& matrix,int dp[310][310], int x, int y)
	{
		int a1 = lr[x][y]; int a2 = ud[x][y];
		int len = min(lr[x][y], ud[x][y]);     // 记为a
		int prev = 0;
		if (x - 1 >= 0 && y - 1 >= 0) {
			prev = dp[x - 1][y - 1];  
		} // prev 就是斜上方元素组成的正方形最大值，记为b
                dp[x][y] = min(len,prev+1);   // 获得 a和b+1的最小值
		ans = max(ans, dp[x][y]);             // ans记录能得到的最大正方形长度
	}

	int maximalSquare(vector<vector<char>>& matrix) {
		int n = matrix.size(); int m = matrix[0].size();
		if (m == 0 || n == 0) return 0;

		memset(lr, 0, sizeof lr);
		memset(ud, 0, sizeof ud);

        // 遍历整个二维矩阵
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
                // 只有元素自己是1的时候才有计算的必要
				if (matrix[i][j] == '0') { continue; }
                // 记录左边和右边到自己连续的1的长度
				if (i != 0) ud[i][j] = ud[i - 1][j] + 1;
				else ud[i][j] = 1;
				if (j != 0) lr[i][j] = lr[i][j - 1] + 1;
				else lr[i][j] = 1;
			}
		}

		int dp[310][310];        //记录每个位置作为右下角能做成的最大正方形的长度
		memset(dp,0,sizeof dp);
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (matrix[i][j] == '0') continue;
				Check(matrix, dp,i, j);
			}
		}

		return ans * ans;   // 返回面积
	}
};

121. 买卖股票的最佳时机 |

在这里插入图片描述

解题思路

核心思想

我们要在最低点买入，在买入之后的最高点卖出。
遍历一遍数组，记录当前遇到的最低价格，同时计算当前价格 - 最低价格的利润，保留最大利润。

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <=1) return 0;
        int buy_price = prices[0];
        int max_profit =0;

        for (int i=0;i<n;i++)
        {
            buy_price = min(buy_price, prices[i]);

            if (prices[i] > buy_price)
            {
                int profit = prices[i] - buy_price;
                max_profit = max(max_profit,profit);
            }
        }
        return max_profit;
    }
};

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

在这里插入图片描述

解题思路

这道题核心是多次买卖股票求最大收益，可以用贪心算法最优解，也可以用动态规划，这里优先推荐贪心（简单、空间 O (1)、效率最高）。

贪心算法思路（最优）
核心思想：只要后一天价格比前一天高，就赚取这一天的差价，所有上涨日的差价累加就是最大收益

为什么可行？因为可以无限次交易，且无手续费，每天的小利润累加 = 持有一整段上涨的总利润。例：[1,2,3,4,5]
(2-1)+(3-2)+(4-3)+(5-4) = 4，和持有到最后一天卖结果完全一样。

步骤：

遍历价格数组，从第 2 天开始
如果当天价格 > 前一天价格，把差价加入总收益
最终总收益就是答案（无收益返回 0）

动态规划思路（拓展）
定义两个状态：

dp[i][0]：第i天不持有股票的最大收益
dp[i][1]：第i天持有股票的最大收益状态转移：
不持有：前一天不持有或前一天持有今天卖出
持有：前一天持有或前一天不持有今天买入
最终答案：最后一天不持有股票的收益（持有股票无法获得最大收益）

代码实现

(1) 使用贪心算法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <=1) return 0;
        int max_profit = 0;

        for (int i=1; i< n; i++)
        {
            if(prices[i] > prices[i-1])
            {
                max_profit += prices[i] - prices[i-1];
            }
        }

        return max_profit;
    }
};

(2) 使用DP算法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <=1) return 0;
        int max_profit = 0;

        vector<vector<int>> dp(n,vector<int>(2)) ;
        dp[0][0] =0; // 第一天不买，不持有
        dp[0][1] =-prices[0];  // 第一天买，持有

        for (int i=1; i<n; i++)
        {
            dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]);   // 第i填不持有利润: max(第i-1天不持有的利润, 第i-1天持有的利润 + 第i 天卖出的利润)
            dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]);   // 第i填持有利润: max(第i-1天持有的利润, 第i-1天不持有的利润 + 第i 天买入)
        }
        //最后一天必须不持有股票
        return dp[n-1][0];
    }
};