有关动态规划

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

引言

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

动规简述

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

举个例子:计算斐波那契数列(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 f[1024][1024], v[1024],w[1024],n,k;  int main() {     cin>>n>>k;     for(int i=1;i<=n;i++)         cin>>v[i]>>w[i];      for(int i=1;i<=n;i++)     {         for(int j=0;j<=k;j++)         {             f[i][j]=f[i-1][j];             if(j>=v[i])                 f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);         }     }     int ans=-1;     for(int i=0;i<=k;i++)         ans=max(ans,f[n][i]);     cout<<ans;     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];     } }

 

 

TRANSLATE with 有关动态规划
COPY THE URL BELOW
有关动态规划
有关动态规划 Back

EMBED THE SNIPPET BELOW IN YOUR SITE 有关动态规划
Enable collaborative features and customize widget: Bing Webmaster Portal
Back

举报
发表评论

相关文章

当前内容话题
  • 0