字符串+动态规划
字符串算法应用动态规划十分常见，最长公共子串、最长公共子序列都需要用这种算法进行。
44. Wildcard Matching
class Solution {public boolean isMatch(String s, String p) {char[] text=s.toCharArray();char[] pattern=p.toCharArray();//模式串的简化 **b***a*b简化为*b*a*bint len=0;boolean flag=true;for(int i=0;i<pattern.length;i++){if(pattern[i]=='*'){if(flag){pattern[len++]=pattern[i];flag=false;}}else{pattern[len++]=pattern[i];flag=true;}}boolean[][] dp=new boolean[s.length()+1][len+1];dp[0][0]=true;//简化后的模式串以*开头时，if(len>0 && pattern[0]=='*')dp[0][1]=true;for(int i=1;i<=text.length;i++){for(int j=1;j<=len;j++){if(text[i-1]==pattern[j-1] || pattern[j-1]=='?')dp[i][j]=dp[i-1][j-1];else if(pattern[j-1]=='*')dp[i][j]=dp[i-1][j] || dp[i][j-1];}}return dp[text.length][len];}
}
10. Regular Expression Matching
class Solution {public boolean isMatch(String s, String p) {int m=s.length(),n=p.length();boolean[][] dp=new boolean[m+1][n+1];dp[0][0]=true;for(int i=1;i<=p.length();i++){if(p.charAt(i-1)=='*')dp[0][i]=dp[0][i-2];}/*a b b b ab*a b *0 1 2a 0 T F Tb 1 F T Tb 2 F F Tb 3 F F T*/for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.')dp[i][j]=dp[i-1][j-1];else if(p.charAt(j-1)=='*') {dp[i][j]=dp[i][j-2];if(p.charAt(j-2)=='.' || s.charAt(i-1)==p.charAt(j-2))dp[i][j]=dp[i][j] || dp[i-1][j];}elsedp[i][j]=false; }}return dp[m][n];}
}
152. Maximum Product Subarray
算法一：
以每个元素为起点向后做乘积运算知道末尾，寻找最大值并保存。这里需要注意连续乘积的范围用long变量保存，算法复杂度O(N^2)
class Solution {public int maxProduct(int[] nums) {int ans=nums[0];long curProduct,maxProduct=Long.MIN_VALUE;for(int i=0;i<nums.length;i++){curProduct=(long) nums[i];maxProduct=curProduct;for(int j=i+1;j<nums.length;j++){curProduct*=nums[j];maxProduct=Math.max(maxProduct,curProduct);if(curProduct==0)break;}ans=(int)Math.max((long)ans,maxProduct);}return ans;}
}
算法二：
以某个元素结尾的当前子数组的最大乘积有三种来源：当前数组元素（只含有一个元素的子数组）、前一个位置的最大乘积当前元素值、前一个位置的最小乘积当前元素值
class Solution {public int maxProduct(int[] nums) {int ans=nums[0];int lastMin=nums[0],lastMax=nums[0];for(int i=1;i<nums.length;i++){int curMax=Math.max(Math.max(nums[i],nums[i]*lastMin),nums[i]*lastMax);int curMin=Math.min(Math.min(nums[i],nums[i]*lastMin),nums[i]*lastMax);lastMin=curMin;lastMax=curMax;ans=Math.max(ans,lastMax);}return ans;}
}
[搭积木]
#include<iostream>using namespace std;
const int N=105,mod=1e9+7;
typedef long long LL;
int label[N][N]; // label[i][j]表示第i层前j个字符中有多少个'X'
LL preSum[N][N]; // preSum[j][k]表示某一层起点j到终点k的方案数总和（二维前缀和）,每一层都需要更新这个二维前缀和数组
LL dp[N][N][N];
int n,m; //n表示层数，m表示每层的积木数量void calPrefixSum(int i)
{for(int j=1;j<=m;j++){for(int k=j;k<=m;k++){preSum[j][k]=(preSum[j-1][k]+preSum[j][k-1]-preSum[j-1][k-1]+dp[i][j][k])%mod;}}
}LL getSum(int x1,int y1,int x2,int y2)
{return (preSum[x2][y2]-preSum[x2][y1-1]-preSum[x1-1][y2]+preSum[x1-1][y1-1])%mod;
}int main(){cin>>n>>m;char str[N];for(int i=n;i>0;i--){cin>>str+1;for(int j=1;j<=m;j++){label[i][j]=label[i][j-1]+(str[j]=='X'?1:0);}}dp[0][1][m]=1;calPrefixSum(0);int res=1;for(int i=1;i<=n;i++) //层遍历{for(int j=1;j<=m;j++) {for(int k=j;k<=m;k++){if(label[i][k]-label[i][j-1]==0){LL &x =dp[i][j][k];x=(x+getSum(1,k,j,m))%mod;res=(res+x)%mod;}}}calPrefixSum(i);}cout<<(res+mod)%mod<<endl;return 0;
}
[M星云拨时钟]
当前时钟上的某个刻度可以看作一个状态，从当前状态可以有两种转移方式，用一个距离数组记录最短距离。BFS保证了出队列时是到达该状态的最短距离
算法一：BFS
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;int dist[N];
int n,k;int main(){cin>>n>>k;memset(dist,-1,sizeof dist);int ans=0;queue<int> q;q.push(0);dist[0]=0;while(q.size()){int tmp=q.front();q.pop();int a=(tmp+1)%n;if(dist[a]==-1){dist[a]=dist[tmp]+1;q.push(a);}int b=(tmp+k)%n;if(dist[b]==-1){dist[b]=dist[tmp]+1;q.push(b);}}for(int i=0;i<n;i++)ans=max(ans,dist[i]);cout<<ans<<endl;return 0;
}
算法二:
动态规划：实际上是BFS的逆过程，dp[i]表示到达当前状态i的最小步数
当前状态i可以从(i-1+n)%n和（i-k+n）%n这两个状态转移而来
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;int dp[N];
int n,k;int main(){cin>>n>>k;memset(dp,0x3f,sizeof dp); //初始化无穷大 0x3f3f3fint ans=0;dp[0]=0;for(int i=1;i<n;i++){dp[i]=min(dp[(i-1+n)%n],dp[(i-k+n)%n])+1;ans=max(ans,dp[i]);}cout<<ans<<endl;return 0;
}
状态压缩+动态规划
1125. Smallest Sufficient Team
这个问题比赛时我试图用暴力方法做：就是先得到技能-人员的二维二值矩阵，然后进行递归组合，再检查每个组合的技能集合能否包含目标技能集合，包含的话选择其中最小的，复杂度太高必然TLE，后来看了状态压缩+动态规划的解法，真的将二进制编码的特性用到了极致。这类解法都是暴力而又十分精巧的解法，一般数据范围比较小。
这个问题可以从图论角度解释：共有 2 n 2^n 2n个结点（n为技能数量，共有 2 n 2^n 2n个组合）和m条边（m个人），在某个节点上沿着某条边（加入一个人）到达其他节点，最少的人实际上在求从0节点的一个最短路径到达 2 n − 1 2^n-1 2n−1这个终点。
这是大神Lee的做法。
class Solution(object):def smallestSufficientTeam(self, req_skills, people):""":type req_skills: List[str]:type people: List[List[str]]:rtype: List[int]"""n=len(req_skills)m=len(people)skill_no={skills:i for i,skills in enumerate(req_skills)}#print(skill_no)dp=[list(range(m)) for _ in range(1<<n)]#print(dp)dp[0]=[]for i ,p in enumerate(people):his_skill=0for skill in p:if skill in skill_no:his_skill |= (1<<skill_no[skill])for skill_set,arrange in enumerate(dp):new_skills=skill_set | his_skill #把这个人加进来的团队技能树if new_skills!= skill_set and len(dp[new_skills])>len(arrange)+1:dp[new_skills]=arrange+[i]return dp[(1<<n)-1]
上述解法还有值得优化的地方，首先有些员工的节能包是其他员工的真子集，还有没有技能的员工，这些员工在搜索的时候应该不需要考虑，所以进行预剪枝。
class Solution {public static ArrayList<Integer> ans;public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {HashMap<String, Integer> skill_no = new HashMap<>();int n = req_skills.length, m = people.size();for (int i = 0; i < n; i++)skill_no.put(req_skills[i], i);int[] skillsBinary = new int[m];int k = 0;for (List<String> p : people) {for (String s : p) {skillsBinary[k] |= (1 << skill_no.get(s));}//System.out.print(skillsBinary[k]+" ");k++;}ans = new ArrayList<>();deleteDuplicate(skillsBinary, n);/*0 1 2mmcmnwacnhhdd vza mrxyc001 000 000 110*/ArrayList<Integer> tmp=new ArrayList<>();backtrace(0,tmp,skillsBinary,n);int[] res = new int[ans.size()];for (int i = 0; i < ans.size(); i++) {res[i] = ans.get(i);}return res;}public static void backtrace(int cur, ArrayList<Integer> curArrange, int[] skillsBinary, int len) {if (cur == (1 << len) - 1) {if (ans.size() == 0 || curArrange.size() < ans.size()) {ans.clear();ans.addAll(curArrange);}return;}if (ans.size() != 0 && curArrange.size() >= ans.size())return;int zeroBitIndex = 0;while (((cur >> zeroBitIndex) & 1) == 1)zeroBitIndex++;for (int i = 0; i < skillsBinary.length; i++) {if (skillsBinary[i] == 0 || ((skillsBinary[i] >> zeroBitIndex) & 1) == 0)continue;//System.out.println(i);curArrange.add(i);backtrace(cur | skillsBinary[i], curArrange, skillsBinary, len);curArrange.remove(curArrange.size() - 1);}}public static void deleteDuplicate(int[] skillsBinary, int len) {for (int i = 0; i < skillsBinary.length - 1; i++) {for (int j = i + 1; j < skillsBinary.length; j++) {if (skillsBinary[i]!=0 && skillsBinary[j]!=0 && isDuplicate(skillsBinary[i], skillsBinary[j], len)){skillsBinary[j] = 0;//System.out.println(i+" haha "+j);}else if (isDuplicate(skillsBinary[j], skillsBinary[i], len)){skillsBinary[i] = 0;//System.out.println(j+" haha "+i);} }}}//a是否包含bpublic static boolean isDuplicate(int a, int b, int len) {for (int i = 0; i < len; i++) {//如果出现a的某一位为0，b的相同位为1if (((a >> i) & 1) == 0 && ((b >> i) & 1) == 1)return false;}//System.out.println(a+" xixi "+b);return true;}
}
91. 最短Hamilton路径
这也是一个NP Complete问题。
import java.util.*;public class Main{public static int N = 21;public static int M = (1 << 20);public static int[][] f;public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[][] weight = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {weight[i][j] = in.nextInt();}}f = new int[M][N]; //f[K][i]状态为K停在i点的最短路径长度for (int i = 0; i < M; i++)Arrays.fill(f[i], Integer.MAX_VALUE);f[1][0] = 0;for (int i = 0; i < (1 << n); i++) { //一共有1<<n个状态 索引为0~2^n-1for (int j = 0; j < n; j++) { //一共有n个状态，索引为0~n-1if (((i >> j) & 1) == 1) { //当下一个状态在第j个点上（意味着对应的二进制表达从低位数的第j位为1）for (int k = 0; k < n; k++) { //枚举到达j的点kif ((((i - (1 << j) )>> k) & 1) == 1) //当前状态为k（第k为必须为1），从k转到jf[i][j] = Math.min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);}}}}System.out.println(f[(1 << n) - 1][n - 1]);}
}
95. 费解的开关
这个问题既有暴力枚举又有递推关系的表达
#include<iostream>
#include<algorithm>
#include<limits.h>using namespace std;const int N=7;
char chess[N][N];
char temp[N][N];int dirR[5]={0,-1,1,0,0};
int dirC[5]={0,0,0,-1,1};void init(){for(int i=0;i<5;i++){for(int j=0;j<5;j++){temp[i][j]=chess[i][j];}}
}void switch_up(int x,int y){for(int i=0;i<5;i++){int x1=x+dirR[i],y1=y+dirC[i];if(x1>=0 && x1<5 && y1>=0 && y1<5)temp[x1][y1]='0'+'1'-temp[x1][y1];}}int solve(){int ans=INT_MAX;for(int state=0;state<(1<<5);state++){int res=0;init();for(int pos=0;pos<5;pos++){if((state>>pos) & 1){res++;switch_up(0,pos);}}for(int i=0;i<4;i++){for(int j=0;j<5;j++){if(temp[i][j]=='0'){res++;switch_up(i+1,j);}}}bool all_on=true;for(int i=0;i<5;i++){if(temp[4][i]=='0'){all_on=false;break;}}if(all_on){//cout<<"haha"<<res<<endl;ans=min(ans,res);//cout<<"xixi"<<ans<<endl;}}return ans<=6?ans:-1;
}int main()
{int n;cin>>n;while(n--){for(int i=0;i<5;i++){cin>>chess[i];//cout<<chess[i]<<endl;}cout<<solve()<<endl;}return 0;
}
Acwing.282. 石子合并
#include<iostream>using namespace std;
const int N=310;
int a[N],dp[N][N],preSum[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){scanf("%d",a+i);preSum[i]=preSum[i-1]+a[i];}for(int len=2;len<=n;len++){ //枚举区间长度（长度至少为2）for(int i=1;i+len-1<=n;i++){int l=i,r=l+len-1; //区间起点和终点，dp[l][r]=1e9;for(int k=l;k<r;k++){ //在当前区间寻找子区间最优切分 k~l,r-1 [l,k] [k+1,r]dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+preSum[r]-preSum[l-1]);}}}cout<<dp[1][n]<<endl;return 0;
}
1000. Minimum Cost to Merge Stones
class Solution {public int mergeStones(int[] stones, int K) {int len=stones.length;int[] preSum=new int[len+1];for(int i=1;i<=len;i++){preSum[i]=preSum[i-1]+stones[i-1];}int[][] dp=new int[len][len];for(int span=K;span<=len;span++){for(int left=0;left+span-1<len;left++){int right=left + span - 1;dp[left][right]=Integer.MAX_VALUE;for(int split=left;split<right;split+=(K-1)){dp[left][right] = Math.min(dp[left][right], dp[left][split] + dp[split + 1][right]);}if((left - right) % (K-1) == 0)dp[left][right] += (preSum[right + 1] - preSum[left]);}}return dp[0][len-1];}
}
1155. Number of Dice Rolls With Target Sum
class Solution {public static int count;public static int mod=(int)1e9+7;public int numRollsToTarget(int d, int f, int target) {int[][] dp=new int[d+1][target+1]; //dp[i][j]表示前i个筛子掷出j点的方案//当f小于target，dp[1][1:f]=1,当f大于target,dp[1][1:target]=1for(int j=1;j<=Math.min(target,f);j++)dp[1][j]=1;for(int dice=2;dice<=d;dice++){for(int curSum=1;curSum<=target;curSum++){for(int k=1;k<=f;k++){if(curSum-k>=1){dp[dice][curSum]=(dp[dice][curSum]+dp[dice-1][curSum-k])%mod;}}}}return dp[d][target];}
}
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
#include<iostream>using namespace std;
const int N=1010;
int a[N];
typedef long long LL;
LL dp[N][N];//dp[i][j]表示前i个数字组成和为j的方案数int main(){int n,sum;cin>>n>>sum;for(int i=1;i<=n;i++){scanf("%d",a+i); //scanf读取速度比cin快}dp[0][0]=1LL; //前0个数和为0的方案数为1 当i>=1时，dp[i][0]始终为0 dp[i][0]for(int i=1;i<=n;i++){for(int j=0;j<=sum;j++){dp[i][j]=dp[i-1][j];if(j>=a[i])dp[i][j]+=dp[i-1][j-a[i]];}}printf("%lld\n", dp[n][sum]);return 0;
}
139. Word Break
算法一：动态规划
class Solution {public boolean wordBreak(String s, List<String> wordList){if (s == null || s.length() == 0) return false;int n = s.length();Set<String> set = new HashSet<>();for (String word : wordList) {set.add(word);}// dp[i] represents whether s[0...i] can be formed by dictboolean[] dp = new boolean[n];for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {String sub = s.substring(j, i + 1);if (set.contains(sub) && (j == 0 || dp[j - 1])){dp[i] = true;break;}}}return dp[n - 1];}
}
算法二：深度优先搜索
class Solution {public static HashMap<String,Boolean> map;public static HashSet<String> set;public boolean wordBreak(String s, List<String> wordDict) {map=new HashMap<>();set=new HashSet<>(wordDict);return dfs(s);}public static boolean dfs(String s){if(s.length()==0)return true;if(map.containsKey(s))return map.get(s);for(int split=1;split<=s.length();split++){if(set.contains(s.substring(0,split)) && dfs(s.substring(split))){map.put(s,true);return true;}}map.put(s,false);return false;}
}
算法二：BFS
class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set=new HashSet<>(wordDict);Queue<String> q=new LinkedList<>();q.add(s);HashSet<String> illegal=new HashSet<>();while(!q.isEmpty()){String cur=q.poll();for(int split=1;split<=cur.length();split++){if(set.contains(cur.substring(0,split))){if(split==cur.length())return true;if(!illegal.contains(cur.substring(split))){q.add(cur.substring(split));illegal.add(cur.substring(split));}}}}return false;}
}
403. Frog Jump
暴力递推解法，自底向上（TLE）：
class Solution {public boolean canCross(int[] stones) {int n=stones.length;if(stones[1]-stones[0]!=1)return false;return recursive(1,1,stones);}public static boolean recursive(int pos,int preStep,int[] stones){if(pos==stones.length-1)return true;boolean canPass=false;for(int j=pos+1;j<stones.length;j++){int step=stones[j]-stones[pos];if(step==preStep)canPass=canPass || recursive(j,preStep,stones);if(step==preStep-1)canPass =canPass|| recursive(j,preStep-1,stones);if(step==preStep+1)canPass=canPass|| recursive(j,preStep+1,stones);}return canPass;}
}
记忆化搜索
class Solution {public boolean canCross(int[] stones) {int n=stones.length;HashSet<Integer>[] record=new HashSet[n]; //上一步步数决定下一步步数，需要记录上一步步数情况，record[i]表示能够到达第i块石头所在位置需要的步数的所以可能的集合for(int i=0;i<n;i++)record[i]=new HashSet<>();record[0].add(0);if(stones[0]+1==stones[1])record[1].add(1);for(int i=2;i<n;i++){ //对于第i块石头的位置，必然是来自第1~i-1块石头转移过来for(int j=i-1;j>=1;j--){int step=stones[i]-stones[j]; //从第j块石头位置到达第i块石头位置所需要的步数if(record[j].contains(step-1) || record[j].contains(step) || record[j].contains(step+1)){record[i].add(step);}}}return record[n-1].size()>0;}
}
1024. Video Stitching
算法一：区间dp,dp[i][j]表示区间填充完[i,j]的最小区间数，区间长度最小为2，时间复杂度为O(TN^2)
首先[i,j]一定是由比它小的区间组成的
class Solution {public int videoStitching(int[][] clips, int T) {int[][] dp=new int[T+1][T+1];for(int i=0;i<=T;i++)Arrays.fill(dp[i],111);for(int[] c:clips){int l=c[0],r=c[1];for(int len=1;len<=T;len++){for(int start=0;start+len<=T;start++){int end=start+len;if(end<=l || start>=r)continue;else if(start>=l && end<=r)dp[start][end]=1;else if(end>l && end<=r)dp[start][end]=Math.min(dp[start][end],1+dp[start][l]);else if(start>=l && end>r)dp[start][end]=Math.min(dp[start][end],dp[r][end]+1);else if(start<l && end>r)dp[start][end]=Math.min(dp[start][end],dp[start][l]+1+dp[r][end]);} }}return dp[0][T]==111?-1:dp[0][T];}
}
算法二：
算法三：桶排序+贪心
class Solution {public int videoStitching(int[][] clips, int T) {int[] dp=new int[T];//dp[i]表示以i为起点的长度条的最远终点for(int[] clip:clips){if(clip[0]>=T || clip[0]>=clip[1])continue;dp[clip[0]]=Math.max(Math.min(T,clip[1]),dp[clip[0]]);}for(int i=1;i<T;i++) dp[i]=Math.max(dp[i-1],dp[i]);int cnt=0;int i=0;while(i<T){if(dp[i]<=i){cnt=-1;break;}i=dp[i];cnt++;}return cnt;}
}
983. Minimum Cost For Tickets
算法一：
class Solution {public static HashSet<Integer> set;public int mincostTickets(int[] days, int[] costs) {set=new HashSet<>();for(int i:days)set.add(i);int[] memo=new int[366];Arrays.fill(memo,Integer.MAX_VALUE);return dp(1,days,costs,memo);}public static int dp(int day,int[] days,int[] costs,int[] memo){if(day>365)return 0;if(memo[day]!=Integer.MAX_VALUE)return memo[day];int ans=Integer.MAX_VALUE;if(set.contains(day)){ans=Math.min(dp(day+1,days,costs,memo)+costs[0],dp(day+7,days,costs,memo)+costs[1]);ans=Math.min(dp(day+30,days,costs,memo)+costs[2],ans);}elseans=dp(day+1,days,costs,memo);memo[day]=ans;return ans;}
}
非递归版如下：dp[i]表示前i天的最小花费，可以由前i-1天的最小花费+一天旅行机票费用，前i-7天的最小花费+七天旅行机票费用，前i-30的最小花费+30天旅行机票费用
class Solution {public static int[] ranges={1,7,30};public int mincostTickets(int[] days, int[] costs) {int[] dp=new int[366];int j=0;for(int i=1;i<366;i++){if(j<days.length && i==days[j]){dp[i]=Math.min(dp[i-1]+costs[0],dp[Math.max(0,i-7)]+costs[1]);dp[i]=Math.min(dp[i],dp[Math.max(0,i-30)]+costs[2]);j++;}elsedp[i]=dp[i-1];}return dp[365];}
}
算法三：
class Solution {public static int[] ranges={1,7,30};public int mincostTickets(int[] days, int[] costs) {int[] memo=new int[days.length];Arrays.fill(memo,Integer.MAX_VALUE);return dp(0,days,costs,memo);}public static int dp(int idx,int[] days,int[] costs,int[] memo){if(idx>=days.length)return 0;if(memo[idx]!=Integer.MAX_VALUE)return memo[idx];int j=idx;int ans=Integer.MAX_VALUE;for(int k=0;k<3;k++){while(j<days.length && days[idx]+ranges[k]-1>=days[j])j++;ans=Math.min(ans,dp(j,days,costs,memo)+costs[k]);}memo[idx]=ans;return ans;}
}