區(qū)間dp

比如從i到j(luò)如果str[i] == str[j]那么i到j(luò)的值就與i+1到j(luò)-1相同，否則從i到j(luò)-1與i+1到j(luò)中選一個(gè)最優(yōu)解，這道題直接定義int的二維數(shù)組會(huì)mle，用short，也可以用滾動(dòng)數(shù)組。

#include<stdio.h> const int maxa = 5005; short dp[maxa][maxa]; char str[maxa]; #define min(a,b) a<b?a:b; int main(){int n;while(scanf("%d", &n)!=EOF){scanf("%s", str);for(int i = 1; i < n; i++){for(int j = 0; j + i < n; j++){if(str[j] == str[j+i]){dp[j][j+i] = dp[j+1][j+i-1];}else{dp[j][j+i] = min(dp[j+1][j+i]+1, dp[j][j+i-1]+1);}}}printf("%d\n", dp[0][n-1]);} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/icodefive/p/4299684.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1159的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。