POJ 1850 递推 也是 dp 的一种啊

本文主要是介绍POJ 1850 递推 也是 dp 的一种啊，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

dp[i][j] 代表 长度 为 i 的 首字母 为 j 的字符串有多少个。

转移就是不停的往现有字符串前边合法的增加字符串

i 代表长度 j 代表 首字母 k 代表可以从上一个的哪个转移过来

	for(int i=0;i<26;i++)dp[1][i]=1;for(int i=2;i<27;i++){for(int j=0;j<26;j++){for(int k=25;k>j;k--)dp[i][j]+=dp[i-1][k];}}	

计算的时候，先统计长度小的

再统计长度相同的， 注意只统计合法的。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>using namespace std;
#define MAX 500
#define INF 0x3f3f3f3f
#define MS(x) memset(x,0,sizeof(x))
#define ll long longll dp[100][100];// length i  front jbool check(char * s)
{int len=strlen(s);int cur=-1;for(int i=0;i<len;i++)if(s[i]<=cur)return false;elsecur=s[i];return true;
}int main()
{for(int i=0;i<26;i++)dp[1][i]=1;for(int i=2;i<27;i++){for(int j=0;j<26;j++){for(int k=25;k>j;k--)dp[i][j]+=dp[i-1][k];}}	char s[100];while(scanf("%s",s)!=EOF){int len=strlen(s);if(!check(s)){cout<<"0"<<endl;continue;}ll ans=0;for(int i=1;i<len;i++)for(int j=0;j<26;j++)ans+=dp[i][j];for(int i=0;i<len;i++){for(int j=0;j<s[i]-'a';j++){if(i!=0&&j<=s[i-1]-'a')continue;ans+=dp[len-i][j];}}cout<<ans+1<<endl;}return 0;
}

这篇关于POJ 1850 递推 也是 dp 的一种啊的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---