Jack DP 滚动数组
Jack
问题描述
题目描述了一个名为“小镇追逐”的游戏场景。游戏中小镇被划分为R × S R \times SR×S的方格，Jack 从左上角出发，目标是到达右下角的“奖励星号”。路径只能向右或向下移动，且不能穿过墙壁（用#表示）。左上角和右下角始终是空地（用.表示）。
输入格式
输入包含Z ZZ个任务。每个任务的第一行包含两个正整数R RR和S SS，表示小镇的行数和列数。接下来的R RR行每行包含S SS个字符，表示小镇的布局。
输出格式
对于每个任务，输出一行语句：
E x i s t u j e X r u z n y c h c e s t . Existuje\ X\ ruznych\ cest.ExistujeXruznychcest.
其中X XX是从左上角到右下角的不同路径数量。路径必须恰好包含R + S − 2 R + S - 2R+S−2步，且不能穿过墙壁。
样例输入
2 22
3 3 3\ 333
. . . ......
KaTeX parse error: Expected 'EOF', got '#' at position 2: .#̲.
. . . ......
1 6 1\ 616
KaTeX parse error: Expected 'EOF', got '#' at position 4: ...#̲..
样例输出
E x i s t u j e 2 r u z n y c h c e s t . Existuje\ 2\ ruznych\ cest.Existuje2ruznychcest.
E x i s t u j e 0 r u z n y c h c e s t . Existuje\ 0\ ruznych\ cest.Existuje0ruznychcest.
题解
题目本质是一个二维dp
dp[i][j] 定义为从起点到点（i，j）的路径数
状态转移方程为：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意到dp[i][j]只和第 i 和 i - 1 行相关
可以用滚动数组进一步优化空间
代码
#include<bits/stdc++.h>usingnamespacestd;staticconstintMOD=1000000007;// 这题其实没说取模，但很多OJ会加；不影响可去掉intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intZ;cin>>Z;while(Z--){intR,S;cin>>R>>S;vector<longlong>dp(S,0);for(inti=0;i<R;i++){string row;cin>>row;for(intj=0;j<S;j++){if(row[j]=='#'){dp[j]=0;// 墙，路径数为0}else{if(i==0&&j==0){dp[j]=1;// 起点}else{longlongfrom_up=dp[j];// 上一行longlongfrom_left=(j>0?dp[j-1]:0);dp[j]=from_up+from_left;}}}}cout<<"Existuje "<<dp[S-1]<<" ruznych cest."<<"\n";}return0;}