動態(tài)規(guī)劃大體可分為：序列類、區(qū)間DP、背包類問題等幾類，主要是需要找到不同維數(shù)組所代表的實際含義（狀態(tài)）、確定狀態(tài)轉(zhuǎn)移方程、并且設(shè)置初始邊界條件，使循環(huán)得以進(jìn)行

創(chuàng)新互聯(lián)于2013年成立，先為新蔡等服務(wù)建站，新蔡等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為新蔡企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

一、序列類

1.大上升子序列（攔截導(dǎo)彈、合唱隊型、藥劑稀釋）

//大上升子序列√
#include#include#include
using namespace std;
const int maxn = 100;
int dp[maxn];
int a[maxn];
int main() {
	int n;
	cin >>n;
	for (int i = 0; i< n; i++) {
		cin >>a[i];
	}
	dp[0] = 1;
	for (int i = 1; i< n; i++) {
		dp[i] = 1;
		for (int j = i - 1; j >= 0; j--) {
			if (a[i] >a[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	int ans = dp[0];
	for (int i = 1; i< n; i++) {
		ans = max(ans, dp[i]);
	}
	cout<< ans<< endl; return 0;
//}

2.大子序列和

大子序列和
#include#include#include
const int maxn = 100;
using namespace std;
int main() {
	int dp[maxn];
	int a[maxn];
	int n;
	cin >>n;
	for (int i = 0; i< n; i++) {
		cin >>a[i];
	}
	dp[0] = a[0];
	for (int i = 1; i< n; i++) {
		dp[i] = max(dp[i - 1] + a[i], a[i]);
	}
	int maxsum = -10;
	for (int i = 0; i< n; i++) {
		maxsum = max(maxsum, dp[i]);
	}
	cout<< maxsum<< endl; return 0;
}

3.雙側(cè)大子序列和（poj）

//雙側(cè)大子段和
#include#include
#includeusing namespace std;
const int maxn = 99999;
const int minn = -99999;
int left_sum[maxn];
int right_sum[maxn];
int a[maxn];
void init(int n) {
	for (int i = 0; i< n; i++) {
		left_sum[i] = minn;
		right_sum[i] = minn;
	}
}
int main() {
	int m;
	cin >>m;
	while (m--) {
		int n;
		cin >>n;
		for (int i = 0; i< n; i++) {
			cin >>a[i];
		}
		init(n);
		left_sum[0] = a[0];
		for (int i = 1; i< n; i++) {
			left_sum[i] = max(left_sum[i - 1] + a[i], a[i]);
		}
		int temp = minn;
		for (int i = 0; i< n; i++) {
			temp = temp >left_sum[i] ? temp : left_sum[i];
			left_sum[i] = temp;
		}
		right_sum[n - 1] = a[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			right_sum[i] = max(right_sum[i + 1] + a[i], a[i]);

		}
		temp = minn;
		for (int i = n - 1; i >= 0; i--) {
			temp = temp >right_sum[i] ? temp : right_sum[i];
			right_sum[i] = temp;
		}
		int ans =minn;
		for (int k = 0; k< n - 1; k++) {
			int v = left_sum[k] + right_sum[k + 1];
			ans = max(ans, v);
		}
		cout<< ans<< endl;
	}
}

二、背包類問題

1.0-1背包問題

0-1背包問題

#include#include#include
#include#includeusing namespace std;
const int maxn = 100;
int main() {
	int dp[maxn][maxn];
	memset(dp, 0, sizeof(dp));
	int N, W;
	cin >>N >>W;
	int w[maxn]; int v[maxn];
	for (int i = 1; i<= N; i++) {
		cin >>w[i] >>v[i];
	}
	for (int i = 1; i<= N; i++) {//一定要注意這里的標(biāo)號，背包問題從1開始方便計算不同的物品編號
		for (int j = w[i]; j<= W; j++) {//for循環(huán)的終止條件
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
	cout<< dp[N][W];
	return 0;

}

2.完全背包問題

//完全背包問題

#include#include#include
#include#includeusing namespace std;
const int maxn = 100;
int main() {
	int dp[maxn][maxn];
	memset(dp, 0, sizeof(dp));
	int n, w;
	cin >>n >>w;
	int w[maxn]; int v[maxn];
	for (int i = 1; i<= n; i++) {
		cin >>w[i] >>v[i];
	}
	for (int i = 1; i<= n; i++) {//一定要注意這里的標(biāo)號，背包問題從1開始方便計算不同的物品編號
		for (int k = 0; k*w[i]<= w; k++) {
			for (int j = k*w[i]; j<= w; j++) {//for循環(huán)的終止條件
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k*w[i]] + k*v[i]);
			}
		}
	}
	cout<< dp[n][w];//怎么輸出k，把上面那個改一下就好，不用max函數(shù)，而用手動的判斷
	return 0;
}
//如果是多重背包，則改為設(shè)置k上限為對應(yīng)的

3.最佳湊單

//最佳湊單：

#include#include
#includeusing namespace std;
const int maxn = 100;
int main() {
	int n, v;
	cin >>n >>v;
	int a[maxn];
	int dp[maxn][maxn];
	int sum = 0;
	for (int i = 1; i<= n; i++) {
		cin >>a[i]; sum += a[i];
	}
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;

	for (int i = 1; i<= n; i++) {
		for (int j = 0; j<= sum; j++) {
			if (j >= a[i]) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]]);

			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j]);
			}
		}
	}
	int now = 0;
	for (now = v; now<= sum; now++) {
		if (dp[n][now])break;
	}
	if (now >sum)cout<< "null";
	else {
		cout<< now;
	}return 0;
}
//還可以與背包問題結(jié)合，假設(shè)有每件有限定額，那么一共有多少種湊法(相當(dāng)于把輸出展開即可）

4.天平問題

//天平問題
#include#include#includeusing namespace std;
int main() {
	int c, g;
	cin >>c >>g;
	int len[21];//力臂長度
	int wei[21];
	int dp[21][15001];
	for (int i = 1; i<= c; i++) {
		scanf_s("%d", &len[i]);
	}
	for (int i = 1; i<= g; i++) {
		scanf_s("%d", &wei[i]);
	}
	memset(dp, 0, sizeof(dp));
	dp[0][7500] = 1;
	
	for (int i = 1; i<= g; i++) {
		for (int j = 0; j<= 15000; j++) {
			if (dp[i-1][j]) {
				for (int k = 1; k<= c; k++) {
					dp[i][j + wei[i] * len[k]] += dp[i - 1][j];
				}
			}
		}
	}
	cout<< dp[g][7500];
	return 0;

}

5.裝載問題

//裝載問題

#include#include#include
#includeconst int maxn = 100;
using namespace std;
int dp[1000][1000];
int a[maxn];
int main() {
	int n;
	cin >>n;
	int sum = 0;
	for (int i = 1; i<= n; i++) {
		cin >>a[i]; sum += a[i];
	}
	int c1, c2;
	cin >>c1 >>c2;

	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (int i = 1; i<= n; i++) {
		for (int j = 0; j<= c1 + c2; j++) {
			if (j >= a[i]) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]]);
			}
			else {
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			}
		}
	}
	int ans1=0;
	for ( ans1 = c1; ans1 >= 0; ans1--) {
		if (dp[n][ans1])break;
	}
	int ans[10]; int num = 0;
	if (sum - ans1 >c2) { cout<< "can't find a way to Loading"<< endl; return 0; }//提前寫好終止條件
	for (int i = n; i >= 1; i--) {//初始的dp[n][ans1]肯定是true
		if (ans1 - a[i] >= 0 && dp[i - 1][ans1 - a[i]] == true) {
			ans[num++] = a[i]; ans1 -= a[i]; a[i] = 0;//先減去再歸為0
		}//把前面的存起來，把后面的正常輸出
	}
	cout<< "ok,can load it"<< endl;
	cout<< "a way is:"<< endl;
	cout<< "the first trip load:";
	for (int i = num - 1; i >= 0; i--) {
		cout<< ans[i]<<' ';
	}
	cout<< endl;
	cout<< "the second trip load:";
	for (int i = 1; i<= n; i++) {
		if (a[i])cout<< a[i]<< ' ';
	}
	return 0;
}

6.貪心盜寶問題（阿里巴巴與四十大盜—）

體會與正宗盜寶問題的區(qū)別

//貪心盜寶（非正規(guī)盜寶法
#includeusing namespace std;
struct treasure {
	int w;//weight
	int v;//value
	int n;//bianhoa
};
treasure t[1000];
bool ok[1000];
int main() {
	int m; int n;
	cin >>m>>n;
	for (int i = 0; i< n; i++) {
		cin >>t[i].w >>t[i].v >>t[i].n;
	}
	//按照value 排序 
	int tempv = 0; int tempn = 0; int tempw = 0;
	for (int i = 0; i< n; i++) {
		for (int j = 0; j< n - i; j++) {
			if (t[j + 1].v >t[j].v) {
				tempw = t[j + 1].w;
				t[j + 1].w = t[j].w;
				t[j].w = tempw;
				tempv = t[j + 1].v;
				t[j + 1].v = t[j].v;
				t[j].v = tempv;
				tempn = t[j + 1].n;
				t[j + 1].n = t[j].n;
				t[j].n = tempn;
			}
		}
	}//實現(xiàn)降序排列
	memset(ok, 0, sizeof(ok));
	int ans = 0;
	for (int i = 0; i< n; i++) {
		if (m >= t[i].w && !ok[t[i].n]) {
			ans += t[i].v;
			m -= t[i].w;
			ok[t[i].n] = 1;
		}
	}
	cout<< ans;
	return 0;
}

6.1盜寶問題

盜寶
先寫個0-1背包
#include//這和0-1背包不完全一樣，0-1背包的橫坐標(biāo)存的是橫坐標(biāo)，還是有這個問題，下標(biāo)可能會超啊
#include
#include#includeconst int maxn = 1000;
int value[maxn][maxn];
int dp[maxn][maxn];
int weight[maxn][maxn];//第i個洞，第幾個作品
int cave[maxn];
using namespace std;
int main() {
	int m = 0; int n = 0;
	cin >>m >>n;
	memset(cave, 0, sizeof(cave));
	int max_cave = 0;
	for (int i = 1; i<= n; i++) {
		int a, b, c;
		max_cave = max(max_cave, c);
		cin >>a >>b >>c;
		value[c][cave[c]] = b;
		weight[c][cave[c]] = a;
		cave[c]++;
	}
	//init：初始化
	for (int i = 1; i<= max_cave; i++) {
		for (int j = 0; j< cave[i]; j++) {
			for (int k = weight[i][j]; k<= m; k++) {
				dp[i][k] = max(value[i][j], dp[i][k]);
			}//承重為大于k時，能獲得的大收益，這個這個寶物對應(yīng)的價值
		}
	}
	//dp
	for (int k = 0; k<= m; k++) {
		for (int i = 1; i<= max_cave; i++) {
			for (int j = 0; j< cave[i]; j++) {
				if (k >= weight[i][j]) {
					//洞內(nèi)物品的更新
					dp[i][k] = max(dp[i][k], dp[i - 1][k - weight[i][j]] + value[i][j]);
					//正常的背包問題，不拿和拿
					dp[i][k] = max(dp[i - 1][k], dp[i][k]);
				}
				else {
					dp[i][k] = max(dp[i - 1][k], dp[i][k]);
				}
			}
		}
	}
	cout<< dp[max_cave][m]<< endl;
	return 0;
}

7.human?genes

//human   genes
#include#include
#include#include#include#include#include#define N 1000
using namespace std;
int s[5][5] = {
	{5,-1,-2,-1,-3},
{-1,5,-3,-2,-4},
{-2,-3,5,-2,-2},
{-1,-2,-2,5,-1},
{-3,-4,-2,-1,-1000}
};
int getint(char c) {
	switch (c)
	{
	case'A': {return 0; break; }
	case 'C': {return 1; break; }
	case'G': {return 2; break; }
	case'T': {return 3; break; }
	case'-': {return 4; break; }
	default:
		break;
	}
}
int dp[N][N];
string str;//t體會到字符串的好處
int main() {
	int n;
	cin >>n;
	while (n--) {
		int n1;
		cin >>n1 >>str;
		int a[101];
		memset(dp, 0, sizeof(dp));
		memset(a, -1, sizeof(a));
		for (int j = 0; j< n1; j++) {
			a[j + 1] = getint(str[j]);
		}
		int n2;
		cin >>n2 >>str;
		int b[101];//數(shù)組要開大qwq
		memset(b, -1, sizeof(b));
		for (int j = 0; j< n2; j++) {
			b[j + 1] = getint(str[j]);
		}
		//注意初始化
		dp[0][0] = 0;
		for (int i = 1; i<= n1; i++) {
			dp[i][0] = dp[i - 1][0] + s[a[i]][4];
		}
		for (int j = 1; j<= n2; j++) {
			dp[0][j] = dp[0][j - 1] + s[4][b[j]];
		}
		for (int i = 1; i<= n1; i++) {
			for (int j = 1; j<= n2; j++) {
				dp[i][j] = max(dp[i - 1][j - 1] + s[a[i]][b[j]], max(dp[i - 1][j] + s[a[i]][4], dp[i][j - 1] + s[4][b[j]]));
			}
		}
		cout<< dp[n1][n2]<< endl;
	}
	return 0;
}

8.tug?of?war（拔河問題）

//tug of war（拔河比賽）重量恰好且數(shù)量恰好的的0-1背包問題
//在裝載基礎(chǔ)上加一個人數(shù)的維度
#include#include
#include#includeusing namespace std;
const int maxr = 100;
const int maxc = 10000;
int dp[maxr][maxc];//裝j個人，達(dá)到k的重量
int a[maxr];
int main() {
	int n;
	cin >>n;
	int total=0;
	for (int i = 1; i<= n; i++) {
		cin >>a[i]; total += a[i];
	}
	int sum = total / 2;
	int person = ceil(n / 2.0);//向上取整
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (int i = 1; i<= n; i++) {
		for (int j = 1; j<= person; j++) {
			for (int k = a[i]; k<= sum; k++) {
				dp[j][k] = max(dp[j][k], dp[j - 1][k - a[i]]);
			}
		}
	}
	int re1 = 0; int re2 = 0;
	for (int i = sum; i >= 0; i--) {
		if (dp[person][i] || dp[person - 1][i]) {
			re1 = i;
			re2 = total - re1;
			break;
		}
	}
	cout<< re1<< ' '<< re2<< endl; return 0;
}

三、區(qū)間DP（遍歷型DP）

1.TO?Europe

遍歷性DP
to europe,遍歷上一個分割點的狀態(tài)
#include#include
#include#include#includeconst int maxn = 99999;
double dp[maxn];
double s[maxn];
int w[maxn];
using namespace std;
int main() {
	int b; int l;
	int n; int d;
	cin >>b >>l >>n;
	while (!(b == 0 && l == 0 && n == 0)) {
		memset(dp, 0, sizeof(dp));
		d = l * 60.0;//以分鐘為單位輸出
		for (int i = 1; i<= n; i++) {
			cin >>w[i] >>s[i];
		}
		dp[0] = 0;
		for (int i = 1; i<= n; i++) {
			double ans = d / s[i] + dp[i - 1];
			int sum = w[i];
			double s_min = s[i];
			for (int k = i - 1; k >= 1; k--) {
				sum += w[k];
				s_min = min(s_min, s[k]);
				if (sum >b) { break; }//用一個循環(huán)遍歷考慮到所有情況
				//保證小于載重
				double temp = d / s_min + dp[k - 1];
				ans = min(ans, temp);
			}
			dp[i] = ans;
		}
		printf("%.1lf\n", dp[n]);
		cin >>b >>l >>n;
	}
}

2.multiplication puzzle

//multiplication puzzle
//區(qū)間DP，遍歷分割點：
#include#include
#includeint n;
const int maxn = 9999;
int dp[maxn][maxn] = { 0 };
int a[maxn] = { 0 };
using namespace std;
int main() {
	cin >>n;
	for (int i = 0; i< n; i++) {
		cin >>a[i];
	}
	for (int i = 0; i< n; i++) {
		dp[i][i] = 0;
	}
	for (int i = 0; i< n - 1; i++) {
		dp[i][i + 1] = 0;
	}
	for (int l = 2; l<= n - 1; l++) {//循環(huán)序列長度
		for (int i = 0; i< n - l; i++) {
			int j = i + l;
			int ans = 1<< 28;
			for (int k = i + 1; k< j; k++) {
				int v = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j];
				ans = min(ans, v);
			}
			dp[i][j] = ans;
		}

	}
	cout<< dp[0][n - 1]<< endl; return 0;
//}

3.石子歸并

解法1

區(qū)間dp
石子歸并dp[i][j]從i到j(luò)合并起來的最小得分
所以其實石子歸并也是
#include#include
#includeusing namespace std;
int num, p[301], sum[301], dp[301][301];
int main() {
	cin >>num;
	for (int i = 1; i<= num; i++) {
		cin >>p[i];
	}
	for (int i = 1; i<= num; i++) {
		dp[0][i] = 0;
		sum[i] = sum[i - 1] + p[i];
	}
	//dp[i][j]代表長度為i的序列，j是從第幾個石子堆開始合并，最后答案就是dp[num][1]
	for (int len = 2; len<= num; len++) {
		for (int i = 1; i<= num - len + 1; i++) {
			dp[len][i] = 1<< 30;
			for (int k = 1; k<= len - 1; k++) {
				dp[len][i] = min(dp[len][i], dp[k][i] + dp[len - k][k + i]);

			}
			dp[len][i] += sum[i + len - 1] - sum[i - 1];
		}
	}
	cout<< dp[num][1]<< endl; return 0;
}

解法2

石子歸并：注意和矩陣合并的算法不是很一樣要做好區(qū)分
#include#include#include
using namespace std;
const int maxn = 100;
int dp[maxn][maxn];
int a[maxn];
int main() {
	int n;
	cin >>n;
	int sum[maxn];
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i<= n; i++) {
		cin >>a[i]; sum[i] = sum[i - 1] + a[i];
	}
	memset(dp, 0, sizeof(dp));
	for (int len = 2; len<= n; len++) {
		for (int i = 1; i<= n-len+1; i++) {
			int j = i + len - 1;
			int ans = 1<< 30;//注意括號j是能取到且必須取到的，這是和上面題的不同
			for (int k = i; k< j; k++) {
				ans = min(ans, dp[i][k] + dp[k + 1][j]);
			}
			dp[i][j] = ans + sum[j] - sum[i - 1];
		}
	}
	cout<< dp[1][n]<< endl; return 0;
}

4.環(huán)形石子歸并

環(huán)形石子歸并
#include#include
#includeusing namespace std;
const int maxn = 100;
int dp[maxn][maxn];
int a[maxn];
int sum[maxn];
int main() {
	//環(huán)形輸入數(shù)組，得到n個合并的大的值
	int n;
	cin >>n;
	for (int i = 1; i<= n; i++) {
		cin >>a[i];
		a[n + i] = a[i];//多輸入一半的數(shù)組
	}
	int sum[maxn * 2];
	memset(sum, 0, sizeof(sum));
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i<= 2 * n; i++) {
		sum[i] = sum[i - 1] + a[i];
	}
	for (int len = 2; len<= n; len++) {
		for (int i = 1; i<= 2 * n - len + 1;i++) {
			int j = len + i - 1;//i多循環(huán)一下
			int ans = 1<< 30;
			for (int k = i; k< j; k++) {
				ans = min(ans, dp[i][k] + dp[k + 1][j]);//
			}
			dp[i][j] = sum[j] - sum[i - 1] + ans;
		}
	}
	int ret = 1<<28;
	for (int i = 0; i<= n; i++) {
		ret = min(ret, dp[i + 1][i + n]);
	}//最后甄選即可
	cout<< ret;
}

5.環(huán)形石子歸并

//括號匹配：區(qū)間DP
#include#include
#include#includeusing namespace std;
const int maxn = 9999;
int dp[maxn][maxn];
string s;
bool match(int i, int j) {//
	return(s[i - 1] == '('&&s[j - 1] == ')') || (s[i - 1] == '['&&s[j - 1] == ']');
}
using namespace std;
void print(int x, int y) {//單拿出來print函數(shù)又能出一個字符串題+遞歸題
	if (x >y)return;//遞歸超范圍
	if (x == y) {//最小化結(jié)構(gòu)單元，統(tǒng)一遼
		//最小化邊界條件
		if (s[x-1] == '(' || s[x-1] == ')') {
			cout<< '('<< ')';
		}
		else
			cout<< "[]";
		return;//記得終止結(jié)尾
	}
	if (match(x, y)) {
		cout<< s[x-1];
		print(x+1, y-1);
		cout<< s[y-1];
	}
	for (int k = x; k< y; k++) {
		if (dp[x][y] == dp[x][k] + dp[k + 1][y]) {
			print(x, k); print(k + 1, y); return;
		}
	}
}
int main() {
	cin >>s;
	int len = s.length();
	for (int i = 1; i<= len; i++) {
		dp[i][i] = 1;//特殊的初始化！！attention！
	}
	for (int i = 1; i< len; i++) {
		dp[i][i + 1] = match(i, i + 1) ? 0 : 2;
	}
	for (int l = 2; l<= len; l++) {
		for (int i = 1; i<= len; i++) {
			int j = i + l-1;//這個題里面由于j并無具體的含義，區(qū)間or區(qū)間端點都可以，所以j的定義很獨特
			if (j >len)break;
			if (match(i, j)) {
				dp[i][j] = dp[i + 1][j - 1];
			}
			else {
				dp[i][j] = j - i + 1;
			}
			for (int k = i; k< j; k++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
			}
		}
	}
	//cout<< dp[1][len];
	print(1, len);
}

6.最長回文子串和最長回文子序列

//子串：連續(xù)的一串序列，子序列：不一定連續(xù)
//最長回文子序列：dp[i][j]=max(dp[i][j-1],dp[i+1][j])（if(s[i]!=s[j])else{dp[i][j]=dp[i+1][j-1]+2;}
#include#include
#includeusing namespace std;
const int maxn = 100100;
struct range {
	int l;
	int r;
	int v;
}o[maxn];
int n;

int bin_search(int st, int l, int r) {
	int m = (l + r) / 2;
	if (o[m].r<= st && o[m + 1].r >st) { return m; }
	if (l == m || o[m].r<= st) { return bin_search(st, m + 1, r); }
	return bin_search(st, l, m - 1);
}

bool cmp(range a, range b) {
	if (a.r == b.r)return a.l< b.l;
	return a.r< b.r;
}
int dp[maxn];
int main() {
	cin >>n;
	int ans = 0; int idx = 0;
	for (int i = 1; i<= n; i++) {
		cin >>o[i].l >>o[i].r >>o[i].v;
	}
	memset(dp, 0, sizeof(dp));
	sort(o + 1, o + 1 + n, cmp);
	for (int i = 1; i<= n; i++) {
		idx = bin_search(o[i].l, 0, i);
		dp[i] = max(dp[i - 1], dp[idx]+o[i].v);
		ans = max(ans, dp[i]);
	}cout<< ans<< endl;
}

#include#include#includeusing namespace std;
const int maxn = 100;
string s;
int dp[maxn][maxn];
using namespace std;
//此處對回文子串的定義是抽出來多少個，而非一定相同
int main() {
	cin >>s;
	int len = s.length();
	for (int i = 0; i< len; i++) {
		dp[i][i] = 1;
	}
	for (int i = 0; i< len - 1; i++) {
		dp[i][i + 1] = s[i] == s[i+1] ? 3 : 2;//單獨一個字母也算回文子串
	}
	for (int l = 2; l< len; l++) {
		for (int i = 0; i= len)break;
			dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];//上一個括號配對不能同時移動
			//如果回文子串定義為抽出若干字母可以構(gòu)成回文子串：
			//if (s[i] == s[j]) {
			//	dp[i][j] += dp[i + 1][j - 1] + 1;//如果首尾相同，那么每個內(nèi)部字符串加上外部的字母又會構(gòu)成新的回文子串
			//}
			//如果是常規(guī)意義必須連續(xù)的話，可以判斷
			if (s[i] == s[j]) {
				int a = i; int b = j;
				while (s[i] == s[j]) {//順便也練習(xí)了，用while實現(xiàn)遞歸判斷的思路
					if (i >= j) { dp[a][b] += 1; break; }//防止i，j改變
					i++; j--;
				}
			}
		}
	}
	cout<< dp[0][len-1];
}

建議配合筆記“食用”~

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：計算概論A代碼總結(jié)Ⅲ（動態(tài)規(guī)劃類）-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://vcdvsql.cn/article18/cdgogp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、靜態(tài)網(wǎng)站、網(wǎng)站設(shè)計、定制開發(fā)、移動網(wǎng)站建設(shè)、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)