从集合的角度来考虑dp问题
寻找某一状态来代表一类东西
dp考虑方式：1.状态表示 f[i] ：（1）集合：所有以i结尾的子段（2) 属性max/min/数量。
2.状态计算——集合的划分。
f[i]=max(0,f[i-1])+nums[i];
class Solution { public: int maxSubArray(vector<int>& nums) { int res=INT_MIN,last=0; for(int i=0;i<nums.size();i++) { int now=max(0,last)+nums[i]; res=max(res,now); last=now; } return res; } }; class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n=triangle.size(); vector<int> f(triangle[n-1].begin(),triangle[n-1].end()),g(n); for(int i=n-2;i>=0;i--) { for(int j=0;j<=i;j++) g[j]=min(f[j],f[j+1])+triangle[i][j]; f=g; } return f[0]; } }; class Solution { public: int minimumTotal(vector<vector<int>>& nums) { int n=nums.size(); vector<vector<long long>> f(2,vector<long long>(n)); f[0][0]=nums[0][0]; for(int i=1;i<n;i++) { for(int j=0;j<=i;j++) { f[i&1][j]=INT_MAX; if(j>0) f[i&1][j]=min(f[i&1][j],f[i-1 & 1][j-1]+nums[i][j]); if(j<i) f[i&1][j]=min(f[i&1][j],f[i-1 & 1][j]+nums[i][j]); } } long long res=INT_MAX; for(int i=0;i<n;i++) res=min(res,f[n-1&1][i]); return res; } }; class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& g) { int n=g.size(),m=g[0].size(); vector<vector<long long>> f(n,vector<long long>(m)); f[0][0]= !g[0][0]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(g[i][j]) continue; if(i>0) f[i][j]+=f[i-1][j]; if(j>0) f[i][j]+=f[i][j-1]; } } return f[n-1][m-1]; } };线性dp
区间dp
背包dp
f[i]表示前i个数的组合情况
s[i-1]表实前i个数中最后一个数
f[0]=1是设置的边界,这个边界非常巧妙，让你在算s[0]和s[0]s[1]时可得到f[2]=2，而且无需判断字长有没有2。这样在算所以f[1]+=f[0],（实际上在算是s[0]这个点）。可以这么认为在一个i长的字符串中，确定前i-1（或i-2）个就确定了全部.
class Solution { public: int numDecodings(string s) { n=s.size(); vector<int> f(n+1); f[0]=1; for(int i=1;i<n;i++) { if(s[i-1]!='0') f[i]+=f[i-1]; if(i>=2) { int a=(s[i-2]-'0')*10+s[i-1]-'0'; if(a>=10 && a<= 26) f[i]+=f[i-2]; } } return f[n]; } };class Solution { public: int rob(int[] nums) { int n=nums.size(); vector<int> f(n+1),g(n+1); for(int i=1;i<=n;i++) { f[i]=max(f[i-1],g[i-1]); g[i]=f[i-1]+nums[i-1]; } return max(f[n],g[n]); } };
300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。集合：所有以i结尾的上升子序列
属性：长度的最大值
状态计算：
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); vector<int> f(n);// for(int i=0;i<n;i++) { f[i]=1; for(int j=0;j<i;j++) if(nums[i]>nums[j]) f[i]=max(f[i],f[j]+1); } int res=0; for(int i=0;i<n;i++) res=max(f[i],res); return res; } };
72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符删除一个字符替换一个字符示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')集合：所有将第一个字符串的前i个字母，变成第二个字符串的前j个字母的方案。
属性：min
状态计算：（考虑最后一步）
insert：f[i,j-1] +1;
delete: f[i-1,j]+1;
replace:(1)f[i-1,j-1]+1;(2)f[i-1,j-1]
class Solution { public: vector<vector<int>> f; int minDistance(string word1, string word2) { int n=word1.size(),m=word2.size(); f=vector<vector<int>>(n+1,vector<int>(m+1)); for(int i=0;i<=n;i++) f[i][0]=i; for(int i=0;i<=m;i++) f[0][i]=i; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f[i][j]=min(f[i-1][j],f[i][j-1])+1; f[i][j]=min(f[i][j],f[i-1][j-1]+(word1[i-1]!=word2[j-1])); } } return f[n][m]; } };518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1示例 2:
输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。示例 3:
输入: amount = 10, coins = [10] 输出: 1
注意:
你可以假设：
0 <= amount (总金额) <= 50001 <= coin (硬币面额) <= 5000硬币种类不超过 500 种结果符合 32 位符号整数
集合：所有由前i种硬币凑出的总钱数等于j的凑法；
属性：数量
状态计算
f[i,j]=f[i-1,j]+f[i-1,j-c]+f[i-1,j-2c]+f[i-1,j-3c]+f[i-1,j-4c]+f[i-1,j-5c]+f[i-1,j-kc];
f[i,j-c]=f[i-1,j-c]+f[i-1,j-2c]+f[i-1,j-3c]+f[i-1,j-4c]+f[i-1,j-5c]+f[i-1,j-kc];
所以有：f[i,j]=f[i-1,j]+f[i,j-c];
变成一维数组：f[j]=f[j]+f[j-c];
class Solution { public: int change(int m, vector<int>& coins) { int n=coins.size(); vector<int> f(m+1); f[0]=1; for(auto c:coins) for(int j=c;j<=m;j++) f[j]+=f[j-c]; return f[m]; } };664. 奇怪的打印机
有台奇怪的打印机有以下两个特殊要求：
打印机每次只能打印同一个字符序列。每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。
示例 1:
输入: "aaabbb" 输出: 2 解释: 首先打印 "aaa" 然后打印 "bbb"。示例 2:
输入: "aba" 输出: 2 解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。提示: 输入字符串的长度不会超过 100。
class Solution { public: int strangePrinter(string s) { if(s.empty()) return 0; int n=s.size(); vector<vector<int>> f(n+1,vector<int>(n+1)); for(int len=1;len<=n;len++) { for(int l=0;l+len-1<n;l++) { int r=l+len-1; f[l][r]=f[l+1][r]+1; for(int k=l+1;k<=r;k++) { if(s[k]==s[l]) f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]); } } } return f[0][n-1]; } };
f[i,j]表示s的前i个字母和p的前j个字母是否匹配。
1.p[j]！=‘*’，f[i,j]=f[i-1,j-1] && (s[i]和p[j]匹配)
