让字符串成为回文串的最少插入次数

暴力递归

int f1(string s, int l, int r) {
	if (l == r)
		return 0;
	if (l + 1 == r)
		return s[l] == s[r] ? 0 : 1;
	if (s[l] == s[r])
		return f1(s, l + 1, r - 1);
	else
		return min(f1(s, l, r - 1), f1(s, l + 1, r)) + 1;
}

记忆化搜索

const int N=5555;

class Solution {
public:
    int dp[N][N];
    int f1(string s, int l, int r) {
	int ans;
    if(dp[l][r]!=-1)
        return dp[l][r];
	if (l == r)
		ans=0;
	else if (l + 1 == r)
	    ans= (s[l] == s[r] ? 0 : 1;
	else if (s[l] == s[r])
		ans= f1(s, l + 1, r - 1);
	else
		ans= min(f1(s, l, r - 1), f1(s, l + 1, r)) + 1;
    dp[l][r]=ans;
    return ans;    
}
    int minInsertions(string s) {
        int n=s.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dp[i][j]=-1;
            }
        }
        return f1(s,0,n-1);
    }

};

动态规划

预测赢家

力扣486

暴力递归

bool predictTheWinner(vector<int>& nums) {
	int sum = 0;
	for (int num : nums) {
		sum += num;
	}
	int n = nums.size();
	int first = f1(nums, 0, n - 1);
	int second = sum - first;
	return first >= second;
}

int f1(vector<int>nums, int l, int r) {
	if (l == r)
		return nums[l];
	if (l == r - 1)
		return max(nums[l], nums[r]);
	//1.玩家1拿走nums[l] l+1,r
	int p1 = nums[l] + min(f1(nums, l + 2, r), f1(nums, l + 1, r - 1));
	//2.玩家1拿走nums[r] l,r-1
	int p2 = nums[r] + min(f1(nums, l + 1, r - 1), f1(nums,l,r-2));
	return max(p1, p2);
}

记忆化搜索

const int N=50;
class Solution {
public:
    int dp[N][N];

    bool predictTheWinner(vector<int>& nums) {
       int sum=0;
       for(int num:nums){
           sum+=num;
       }
			 int n=nums.size();
       for(int i=0;i<n;i++){
				 for(int j=0;j<n;j++){
					 dp[i][j]=-1;
				 }
			 }
       int first=f2(nums,  0,  n-1);
       int second=sum-first;
       return first>=second;
    }
    int f2(vector<int>nums, int l, int r) {
	if (dp[l][r] != -1)
		return dp[l][r];
	int ans;
	if (l == r)
		ans= nums[l];
	else if (l == r - 1)
		ans= max(nums[l], nums[r]);
	else {
		//1.玩家1拿走nums[l] l+1,r
		int p1 = nums[l] + min(f2(nums, l + 2, r), f2(nums, l + 1, r - 1));
		//2.玩家1拿走nums[r] l,r-1
		int p2 = nums[r] + min(f2(nums, l + 1, r - 1), f2(nums, l, r - 2));
		ans = max(p1, p2);
	}
	dp[l][r] = ans;
	return ans;
  }
};

括号配对

牛客：括号区间配对

如何转移：

记忆化搜索

#include <iostream>
#include<string>
#include <cstring>
#include <climits>
#include <cmath>
#include <vector>
using namespace std;
const int N=222;
int dp[N][N];

int f(string s,int l,int r){
    if(l==r)
        return 1;
    if(l==r-1){
        if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
            return 0;
       
         return 2;
    }
    if(dp[l][r]!=-1)
        return dp[l][r];
    
    int p1=INT_MAX;
    //可能性1: L R本来配对
    if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
        p1=f(s,l+1,r-1);
    int p2=INT_MAX;
    //可能性2:基于每个可能的划分点做划分
    for(int m=l;m<r;m++){
        p2=min(p2,f(s,l,m)+f(s,m+1,r));
    }
    int ans=min(p1,p2);
    dp[l][r]=ans;
    return ans;
}

int main() {
    string s;
    cin>>s;
    int n=s.size();
    memset(dp,-1,sizeof(dp));
    cout<<f(s,0,n-1)<<endl;

}

涂色

转移与依赖

力扣：奇怪的打印机

const int N=222;

class Solution {
public:
    int dp[N][N];

    int strangePrinter(string s) {
        int n=s.size();
        dp[n-1][n-1]=1;
        for(int i=0;i<n-1;i++){
            dp[i][i]=1;
            dp[i][i+1]=s[i]==s[i+1]?1:2;
        }

        for(int l=n-3;l>=0;l--){
            for(int r=l+2;r<n;r++){
                if(s[l]==s[r])
                   dp[l][r]=dp[l][r-1];
                else{
                    int ans=INT_MAX;
                    for(int m=l;m<r;m++){
                        ans=min(ans,dp[l][m]+dp[m+1][r]);
                    dp[l][r]=ans;
                }
              }
            }
        }
        return dp[0][n-1];
    }
};

 洛谷：涂色

合唱队

洛谷

#include <iostream>
#include<string>
#include <cstring>
#include <climits>
#include <cmath>
#include <vector>
using namespace std;
const int N=1111;
int dp[N][N][2];
const int mod = 19650827;
int nums[N];

int main() {
   int n;
   cin>>n;
   for(int i=1;i<=n;i++){
     cin>>nums[i];
   }
    for(int i=1;i<n;i++){
        if(nums[i]<nums[i+1]){
            dp[i][i+1][0]=1;
            dp[i][i+1][1]=1;
        }
    }
    for(int l=n-1;l>=1;l--){
        for(int r=l+2;r<=n;r++){
            if(nums[l]<nums[l+1])
                dp[l][r][0]=(dp[l][r][0]+dp[l+1][r][0])%mod;
            if(nums[l]<nums[r])
                dp[l][r][0]=(dp[l][r][0]+dp[l+1][r][1])%mod;
            if(nums[r]>nums[l])
                dp[l][r][1]=(dp[l][r][1]+dp[l][r-1][0])%mod;
            if(nums[r]>nums[r-1])
                dp[l][r][1]=(dp[l][r][1]+dp[l][r-1][1])%mod;
        }
    }
    cout<<(dp[1][n][0]+dp[1][n][1])%mod;
}