大意不再赘述。
思路:比较简单,当前决策向下走或者上右走,状态方程也比较容易写出,边界条件也可以很好的写出来。
如果将问题扩展一下,要满足最短路径的路径条数呢?如果是多个人一起走,使得总的路程最小呢?动态规划还能有效地求解吗?留给大家思考哦。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <ctype.h> using namespace std; const int MAXN = 400; bool G[MAXN][MAXN]; char str[MAXN]; int d[MAXN][MAXN]; int R, C; void init() { memset(G, 1, sizeof(G)); memset(d, 0, sizeof(d)); } void read_case() { int u; scanf("%d%d%", &R, &C); for(int i = 1; i <= R; i++) { scanf("%d", &u); gets(str); //吃掉了一个换行符,所以从一开始循环 for(int j = 1, v = 0; j <= strlen(str); j++) { if(isdigit(str[j])) { v = v*10 + str[j] - '0'; } else { G[u][v] = 0; v = 0; } } } } int dp() { d[R][C] = 1; G[R][C] = 0; for(int i = R; i >= 1; i--) { for(int j = C; j >= 1; j--) if(G[i][j]) { d[i][j] = d[i+1][j] + d[i][j+1]; } } return d[1][1]; } void solve() { init(); read_case(); int ans = dp(); printf("%d\n", ans); } int main() { int T; scanf("%d%*c", &T); while(T--) { solve(); if(T) printf("\n"); } }