算法3：动态规划简单学习

蔚落 2023-03-01 14:57 92阅读 0赞

动态规划有着非常广阔的应用，此处列举几个典型的应用，同时保持更新，自我学习。

## leetcode 5 最长回文子串 ##

**给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000**  
动态规划 DP问题，建立一个二维数组，dp\[i\]\[j\] 表示s\[i\] ~ s\[j\] 子串，在二维数组中的对角线上都可以看做为只有自身一个字符的单个回文串，所以将其置为1，所以判断是否为回文子串的时候，我们只需要判断右上方部分就可以。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dKUUpGSg_size_16_color_FFFFFF_t_70][]

string LonggestPalindrome(string s)
    {
        
    	int len = s.length();
    	if(len == 0 || len == 1)
    	{
        
    		return s;
    	}
    	int start = 0;//回文串起始位
    	int max = 1;//回文串最大值
    	vector<vector<int>> dp(len,vector<int>(len));//定义二维数组
    	for(int i = 0;i < len ; i++)//初始化状态
    	{
        
    		dp[i][i] = 1;
    		if(i < len - 1 && s[i] == s[i+1])// 判断是否有相邻的两个字符相等
    		{
        
    			 dp[i][i+1]=1;
                 max=2;
                 start=i;
    		}
    	}
    	for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
            {
        
                for(int i=0;i+l-1<len;i++)
                {
        
                    int j=l+i-1;//终止字符位置
                    if(s[i]==s[j]&&dp[i+1][j-1]==1)//状态转移
                    {
        
                        dp[i][j]=1;
                        start=i;
                        max=l;
                    } 
                }
            }
            return s.substr(start,max);//获取最长回文子串
    }

## leetcode 64 最小矩阵路径规划问题 ##

动态规划善于利用空间换时间，构造另外一个二维数组来存储每一步最优的选择，以求最后达到最优的效果。

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

## leetcode 121 股票买卖问题： ##

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

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。  
注意：你不能在买入股票前卖出股票。  
**动态规划：最大利润 = max（前期最大利润，当前价格 - 最小价格）；**

int maxProfit(vector<int>& prices) {
        
            if(prices.size() == 0) return 0;
            int minprice = prices[0];
            int maxprofie = 0;
            for(int i = 1; i < prices.size(); i++)
            {
        
                if(minprice > prices[i])
                {
        
                    minprice = prices[i];
                } 
                maxprofie = max(maxprofie,prices[i] - minprice);
            } 
            return maxprofie;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dKUUpGSg_size_16_color_FFFFFF_t_70]: /images/20230208/88bc76ecdaaa4a4faafe43ac73846dc4.png