题意：已知昨天天气与今天天气状况的概率关系（wePro），和今天天气状态和叶子湿度的概率关系(lePro)
第一天为sunny 概率为 0.63,cloudy 概率 0.17,rainny 概率 0.2.
给定n天的叶子湿度状态，求这n天最可能的天气情况
分析：概率dp
设 dp[i][j] 表示第i天天气为j的最大概率，
pre[i][j]表示第i天天气最可能为j的前一天天气，
dp[i][j]=max(dp[i-1][k]+log(wePro[k][j])+log(lePro[j][lePos[i]])) (k=0,1,2 表示昨天的天气）
注：由于概率越乘越小，考虑精度原因，用log取对数
log(a*b*c) = log a + log b +log c
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 char yezi[5][10]= {"Dry","Dryish","Damp","Soggy"}; 5 char wea[4][10]= {"Sunny","Cloudy","Rainy"}; 6 double yeP[3][4]= {0.6,0.2,0.15,0.05, 7 0.25,0.3,0.2,0.25, 8 0.05,0.10,0.35,0.50 9 }; 10 double weaP[3][3]= {0.5,0.375,0.125, 11 0.25,0.125,0.625, 12 0.25,0.375,0.375 13 }; 14 double init[3]= {0.63,0.17,0.2}; 15 double dp[51][3],pre[51][3]; 16 int n; 17 double maxp; 18 int Pos[51]; 19 void solve() 20 { 21 for(int i=0; i<3; i++) 22 { 23 dp[1][i]=log(init[i])+log(yeP[i][Pos[1]]); 24 //第1天天气为i的概率=初始的天气为i的概率*（第一天叶子为Pos[1]的的状态下天气为i的概率） 25 } 26 for(int i=2; i<=n; i++) // 27 { 28 for(int j=0; j<3; j++) //天气 29 { 30 double maxp=-1e8; 31 int pos=0;//记录天气 32 for(int k=0; k<3; k++) //第i-1天天气为k 33 { 34 double temp=dp[i-1][k]+log(weaP[k][j])+log(yeP[j][Pos[i]]); 35 //昨天天气为k的概率*昨天天气为k今天天气为j的概率*叶子状态为Pos[i]时天气为j的概率 36 if(temp>maxp) 37 { 38 maxp=temp; 39 pos=k;//记录最有可能的天气状况为k 40 } 41 } 42 dp[i][j]=maxp;//第i天天气状况为j的概率 43 pre[i][j]=pos; //表示第i天天气最可能为j的前一天天气 44 } 45 } 46 } 47 int main() 48 { 49 int k=0; 50 int T; 51 char yeC[10]; 52 scanf("%d",&T); 53 while(T--) 54 { 55 k++; 56 printf("Case #%d: ",k); 57 scanf("%d",&n); 58 for(int i=1; i<=n; i++) 59 { 60 scanf("%s",yeC); 61 for(int j=0; j<4; j++) 62 if(strcmp(yeC,yezi[j])==0) 63 { 64 Pos[i]=j; 65 break; 66 } 67 } 68 solve(); 69 double maxp=-1e8; 70 int ans[51]; 71 for(int i=0; i<3; i++)//第n天最有可能的天气 72 if(dp[n][i]>maxp) 73 { 74 maxp=dp[n][i]; 75 ans[n]=i; 76 } 77 for(int i=n-1;i>=1;i--) 78 ans[i]=pre[i+1][ans[i+1]]; //由最后一天往前找每天的天气状况记录在ans 中 79 for(int i=1;i<=n;i++) 80 printf("%s ",wea[ans[i]]); 81 } 82 return 0; 83 }
资料扩展：详情点此
本题属于 隐马尔可夫模型
马尔可夫模型:统计模型，每个状态只依赖于之前的状态
马尔可夫模型可用马尔可夫过程描述
我们就为上面的一阶马尔科夫过程定义了以下三个部分：
状态：晴天、阴天和下雨
初始向量：定义系统在时间为0的时候的状态的概率
状态转移矩阵：每种天气转换的概率
所有的能被这样描述的系统都是一个马尔科夫过程。
隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型，用来描述一个含有隐含未知参数的马尔可夫过程。
包含隐藏状态 （如：天气状态）和 可观状态（如：叶子的湿度）
可以观察到的状态序列和隐藏的状态序列是概率相关的