【以下内容仅为本人在学习中的所感所想，本人水平有限目前尚处学习阶段，如有错误及不妥之处还请各位大佬指正，请谅解，谢谢！】
引言
通过目前参与的各类比赛和网友的面经，不难发现动态规划一直是各类竞赛和面试中的高频和难点，但其最优化的思想在生产生活中的各大领域都具有许多作用。撰写这篇随笔的目的既是为了自我学习的总结，也是为了能得到更多的帮助与见解，从而提高自己。在此，我将以自己的想法叙述我解决动规的过程。
动规简述
动态规划本质是记忆化搜索，即记录之前行为所产生的结果，这也是其比纯搜索算法更快的原因。
举个例子：计算斐波那契数列（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]; } }
