• 有关动态规划


    【以下内容仅为本人在学习中的所感所想,本人水平有限目前尚处学习阶段,如有错误及不妥之处还请各位大佬指正,请谅解,谢谢!】

    #Updated【2022.4.27 修正所附(01背包)代码的错误】

    引言

    通过目前参与的各类比赛和网友的面经,不难发现动态规划一直是各类竞赛和面试中的高频和难点,但其最优化的思想在生产生活中的各大领域都具有许多作用。撰写这篇随笔的目的既是为了自我学习的总结,也是为了能得到更多的帮助与见解,从而提高自己。在此,我将以自己的想法叙述我解决动规的过程。

    动规简述

    动态规划本质是记忆化搜索,即记录之前行为所产生的结果,这也是其比纯搜索算法更快的原因。

    举个例子:计算斐波那契数列(f[n] = f[n – 1] + f[n – 2]),当我们要计算f[8]时,会使用之前已经算过的f[6]与f[7]直接相加得到答案,而不是再从f[0]开始从头计算一遍每个值,这样当数据量很庞大时就可以节省很多时间。

    动规特征

      1.    重叠子问题:每一步,在操作上都具有明显的相同相似性。

      2.    最优子结构:最终问题的最优解基于每一步的最优解而得出。

    解体步骤

    • 大化小;将完整的问题划分到每一步
    • 分情况定变量,将每一步可做的选择列出;一般用数组值代表最终问题的答案,数组每个索引表示影响到最终答案的变量,类似于自变量与因变量。
    • 推方程;在每一个选择的基础上推出当前一步与上一步(或前几步)间的关系
    • 定边界;预处理边界,给定初始值

     

    步骤一:大化小

    官方称法为划分子问题。一般地,我们将每一次操作视为一个子问题,既然满足重叠子结构,那么针对每一次操作,处理方式理应是相同或相似的;在最优子结构的性质下,只要得出每一次操作的最优解,就能递推出最终问题的最优解。

    如:

    (1)01背包

    题意:有N件物品,一个容量为V的背包,其中第i件物品价值为w[i],所占空间为v[i],如何选择物品使得其不超过容量的同时价值最大。

    划分:最终问题是如何选择,最终选择的结果来源于每一次选择,其关键在于每次选择哪一个物品,那么就把每次选择视为一个子问题。并且每次的选择总是以最小空间换最大价值的最优方式进行,即针对每次选择,处理方式相同。

     

    (2)买卖股票

    题意:在每一天,你可以决定是否购买或出售股票。你在任何时候最多只能持有一股股票。你也可以当天购买,然后在当天出售,求最大利润。 

    划分:最终问题是如何让利润最大,最终利润来源于每天的利润,其关键在于如何在每一天选择(买、卖、不买不卖)让利润最大,那么就把每天的操作视为一个子问题。并且每次选择总以最大利润为基础进行操作,每次选择处理方式相同。 

      来源:力扣(LeetCode)

      链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

     

    (3)最长回文子串

    题意:给定一个字符串s,找到s中最长的回文子串

     

    划分:最终问题是如何让回文子串最长,最终的回文串最长基于回文串的字回文串最长,问题的关键在于如何判断某子串是不是回文串,那么就把每次判断视为一个子问题。并且每次判断总是记录最大回文子串,每次处理方式相同。

      来源:力扣(LeetCode)

      链接:https://leetcode-cn.com/problems/longest-palindromic-substring/

     

    (4)编辑距离

    题意:给定两个单词word1和word2,请返回将word1转换成word2所使用的最少操作数。可以对一个单词进行如下三种操作:插入、删除、替换一个字符。

    划分:最终问题为求最少操作数,最终的操作数基于每次字符的操作数,其关键在于两个字符串中当前所选定的两个字符是否相同,那么就把每一次判断视为一个子问题。并且每次判断总是选择最少的操作次数进行执行,每次处理方式相同。

      来源:力扣(LeetCode)

      链接:https://leetcode-cn.com/problems/edit-distance

     

    步骤二:分情况,定变量

    针对划分出的结果,对每一次操作(选择或判断等操作)列出所有可能的情况。

    如:

    (1)01背包

    划分:最终问题是如何选择,最终选择的结果来源于每一次选择,其关键在于每次选择哪一个物品,那么就把每次选择视为一个子问题。并且每次的选择总是以最小空间换最大价值的最优方式进行,即针对每次选择,处理方式相同。

     

    定变量:我们需要记录所选择的物品数,以及当前所用的空间,存在两个变量故需要一个二维数组,数组值表最终问题的答案即最大价值,每个维度的索引代表一个变量,用f[i][v]表示,选择了前i件物品,且在所占空间为v(不超过v)的情况下所产生的最大价值。

     

    (2)买卖股票

    划分:最终问题是如何让利润最大,最终利润来源于每天的利润,其关键在于如何在每一天选择(买、卖、不买不卖)让利润最大,那么就把每天的操作视为一个子问题。并且每次选择总以最大利润为基础进行操作,每次选择处理方式相同。

          

    定变量:由于每天最多只能持有一股,所以我们需要记录当前持有股票的状态即持股或不持股,以及当前所过的天数,数组值代表最终问题的答案即最大利润,每个维度的索引代表一个变量,用f[i][flag]表示,从0到i天所获得的最大利润。由于持股状态需要继续分情况,所以会有两个数组f[i][0],f[i][1]分别表示从0到i天,当前持股/不持股时,所获得的最大利润。

     

    (3)最长回文子串

    划分:最终问题是如何让回文子串最长,最终的回文串最长基于回文串的字回文串最长,问题的关键在于如何判断某子串是不是回文串,那么就把每次判断视为一个子问题。并且每次判断总是记录最大回文子串,每次处理方式相同。

          

    定变量:对于一个子串而言,如果它是回文串,并且长度大于2,那么将它首尾的两个字母去除之后,它仍然是个回文串。所以两个变量首字符与尾字符会影响结果。我们已经知道了某字符串是否为回文串,那么只需要记录首尾字符是否相同,利用拼接法(将首尾字符拼接到上面提到的某字符串上)进行判断,用f[i][j]表示从i到j的字符串是否为回文串,判断首位i与末尾j是否相同即可。

     

    (4)编辑距离

    划分:最终问题为求最少操作数,最终的操作数基于每次字符的操作数,其关键在于两个字符串中当前所选定的两个字符是否相同,那么就把每一次判断视为一个子问题。并且每次判断总是选择最少的操作次数进行执行,每次处理方式相同。

          

    定变量:判断当前的操作方式,首先需要判断当前两个字符是否相同,相同则不操作,不同则选择操作次数最少的一种方式。所以两个变量i与j会影响结果,我们需要记录从word1的0到i位转化为从word2的0到j位所需要的最少操作次数,判断当前两个位置上的字符是否相同即可。用f[i][j]表示从word1的0到i位变为word2的0到j位所需要额最少操作次数。

     

    步骤三:推方程

    列出所有情况后,针对每种情况,推导出相应的状态转移方程,即如何得出在本次操作执行完后的当前最优解。

    (1)01背包

    划分:最终问题是如何选择,最终选择的结果来源于每一次选择,其关键在于每次选择哪一个物品,那么就把每次选择视为一个子问题。并且每次的选择总是以最小空间换最大价值的最优方式进行,即针对每次选择,处理方式相同。

      

    (2)买卖股票

    划分:最终问题是如何让利润最大,最终利润来源于每天的利润,其关键在于如何在每一天选择(买、卖、不买不卖)让利润最大,那么就把每天的操作视为一个子问题。并且每次选择总以最大利润为基础进行操作,每次选择处理方式相同。

     

    (3)最长回文子串

    划分:最终问题是如何让回文子串最长,最终的回文串最长基于回文串的字回文串最长,问题的关键在于如何判断某子串是不是回文串,那么就把每次判断视为一个子问题。并且每次判断总是记录最大回文子串,每次处理方式相同。

     

    (4)编辑距离

    划分:最终问题为求最少操作数,最终的操作数基于每次字符的操作数,其关键在于两个字符串中当前所选定的两个字符是否相同,那么就把每一次判断视为一个子问题。并且每次判断总是选择最少的操作次数进行执行,每次处理方式相同。

     

     

    步骤四:定边界

    数组索引从0开始,在上述递推式中发现如果索引变量从0开始,会出现负索引的情况,所以我们需要对无法计算到的值进行预处理,直接赋上相应的结果。

    如:

    (1)01背包

    注意到循环遍历从1开始,则需要对索引为0时的结果进行预处理f[0][v] = 0;

      (2)  买卖股票

    同理:f[0][0] = 0,f[0][1] = -prices[0];

      (3)  最长回文子串

    某些特殊情况下可能涉及到初始化一个序列,本题中单个字符一定是回文串,所以将所有的单个字符的结果全部初始化f[i][i] =  true,f[j][j]= true;

    (4)编辑长度

    本题中当索引为0时,无法进行访问计算,所以需要对索引为0的所有情况进行初始化f[i][0] = i,f[0][j] = j;

    一般地,初始化边界时可能只需要对某几个量进行初始化赋值,也可能对某一序列进行初始化赋值,视情况而定。

     

    总结

    个人认为,动态规划的关键在于对每一步进行情况划分(即步骤二)。有些时候我们觉得动态规划难,并不是因为推导状态转移方程难,更多的是我们没能将每一种情况划分清楚,不知道每一步有多少种可能的选择,从而导致了我们无法准确推导出方程。动态规划确实比较难掌握,需要我们一步一步去积累,学习是艰苦的也是快乐的,脚踏实地相信我们终能成为理性中的我们,让我们一起努力!

    【感谢您可以抽出时间阅读到这里,第一篇博客可能会有许多不妥之处;受限于水平,许多地方可能存在错误,还请各位大佬留言指正,请见谅,谢谢!】

     

    #附文中所提到的4个题目的代码

    (1)01背包

    复制代码
    #include <bits/stdc++.h>
    using namespace std;
    int n,v,c[102],w[102],f[102][100000];
    
    int main() {
        cin>>n>>v;    
        for(int i = 1 ;i<=n ;i++)
            cin>>w[i];    
        for(int i = 1 ;i<=n ;i++)
            cin>>c[i];    
        for(int i = 1 ;i<=n; i++) {
            for(int j = 1; j<=v ;j++) {
                f[i][j] = f[i-1][j];
                if(j-w[i]>=0)
                    f[i][j] = max(f[i-1][j-w[i]]+c[i],f[i][j]);
            }        
        }    
        cout<<f[n][v]<<endl; 
        return 0;
    }
    复制代码

     

    (2)买卖股票

    复制代码
    public class Solution {
        public int MaxProfit(int[] prices) {
            int[,] profit = new int[prices.Length, 2];
            profit[0, 1] = -prices[0];
            profit[0, 0] = 0;
            for(int i = 1; i < prices.Length; i++) {
                profit[i, 1] = Math.Max(profit[i - 1, 1], profit[i - 1, 0] - prices[i]);
                profit[i, 0] = Math.Max(profit[i - 1, 0], profit[i - 1, 1] + prices[i]);
            }
            return profit[prices.Length - 1, 0];
        }
    }
    复制代码

     

    (3)最长回文子串

    复制代码
    public class Solution {
        public string LongestPalindrome(string s) {
            int len = s.Length, begin = 0, maxLen = 1;
            if(len < 2) return s;
            bool[,] dp = new bool[len, len];//[i, j]是否为回文串
            for(int i = 0; i < len; i++) dp[i, i] = true;
            for(int L = 2; L <= len; L++)
            {
                for(int i = 0; i < len; i++)//L = j - i + 1;
                {
                    int j = L + i - 1;
                    if(j >= len) break;
                    if(s[i] != s[j]) dp[i, j] = false;
                    else
                    {
                        if(j - i < 3) dp[i, j] = true;
                        else dp[i, j] = dp[i + 1, j - 1];
                    }
                    if(dp[i, j] && j - i + 1 > maxLen)
                    {
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.Substring(begin, maxLen);
        }
    }
    复制代码

     

    (4)编辑距离

    复制代码
    public class Solution {
        public int MinDistance(string word1, string word2) {
            int n = word1.Length, m = word2.Length;
            int[,] cost = new int[n + 1, m + 1];
            for(int i = 0; i <= n; i++) cost[i, 0] = i;
            for(int j = 0; j <= m; j++) cost[0, j] = j;
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++) {
                    if(word1[i - 1] == word2[j - 1]) cost[i, j] = cost[i - 1, j - 1];
                    else cost[i, j] = Math.Min(cost[i - 1, j - 1], Math.Min(cost[i, j - 1], cost[i - 1, j])) + 1;
                }
            return cost[n, m];
        }
    }
    复制代码

     

  • 相关阅读:
    JOSEF约瑟 JD3-40/23 JD3-70/23漏电继电器 AC220V\0.05-0.5A
    python基础07——函数,想重复使用自己的代码就写个函数吧
    OpenShift 4 - 用 Percona XtraDB Cluster 在 OpenShift 部署运行 MySQL 多副本集群
    插入排序(直接、二分)
    【微软漏洞分析】MS10-013 Microsoft DirectShow 中的漏洞可能允许远程执行代码
    NLTK(自然语言工具包)
    Havoc插件编写
    JPA Audit and Envers
    C++校园导游程序及通信线路设计
    5_SqlSugar实体中的细节
  • 原文地址:https://www.cnblogs.com/PaperHammer/p/16187703.html