偶然发现一个题目的特殊解法

潮汐

题目是这样的：有一个 [size=1.21em]n×mn×m 的网格，每个格子中有一个正整数。从网格的左上角 [size=1.21em](1,1)(1,1) 出发，每次只能向右或向下移动，到达右下角 [size=1.21em](n,m)(n,m)。求经过的格子数字之和最小的路径和。
第一行两个整数 [size=1.21em]n,mn,m
接下来 [size=1.21em]nn 行，每行 [size=1.21em]mm 个正整数，表示网格中的数字
正常使用DP因该长这样：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int INF=0x3f3f3f3f;
   
4. int main(){
   
5.         int n,m;
   
6.         cin>>n>>m;
   
7.         vector< vector<int> >dp(n+1, vector<int>(m+1,INF));
   
8.         vector< vector<int> >grid(n+1,vector<int>(m+1));
   
9.         dp[0][1]=0;
   
10.         dp[1][0]=0;
    
11.         for(int i=1;i<=n;i++){
    
12.                 for(int j=1;j<=m;j++){
    
13.                         cin>>grid[i][j];
    
14.                         dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j];
    
15.                 }
    
16.         }
    
17.         cout<<dp[n][m];
    
18. }

复制代码

如果有问题告诉我因为我这个没验证
然后我偶然吧输入时的grid[j]输成了grid[n][m]然后答案对了
试了好多个之后都对了，然后我就改成了这样：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int INF=0x3f3f3f3f;
   
4. int main(){
   
5.         int n,m,flag;
   
6.         cin>>n>>m;
   
7.         vector< vector<int> >dp(n+1, vector<int>(m+1,INF));
   
8.         dp[0][1]=0;
   
9.         dp[1][0]=0;
   
10.         for(int i=1;i<=n;i++){
    
11.                 for(int j=1;j<=m;j++){
    
12.                         cin>>flag;
    
13.                         dp[i][j]=min(dp[i][j-1],dp[i-1][j])+flag;
    
14.                 }
    
15.         }
    
16.         cout<<dp[n][m];
    
17. }

复制代码

然后还是对的，这样就省掉了一个二维数组

潮汐

补一下题目，有一点问题：有一个 n×m 的网格，每个格子中有一个正整数。从网格的左上角 (1,1) 出发，每次只能向右或向下移动，到达右下角 (n,m)。求经过的格子数字之和最小的路径和。