因为我自己思考的时候是想的 dp[i][j]表示前i组完成前j步需要的最小步数 这个和大家想的都一样,我就按照惯性思维进行先组后步骤进行遍历求解 下面是我的代码, 之后wa了两个点 我想不出哪有问题,然后看了一下题解发现大家都是先n 后m 我还是有点想不通为什么我这个不行
#include <iostream>
#include <string.h>
#define INF 100000000
using namespace std;
int n, m;
int arr[ 2005 ][ 2005 ];
long long dp[ 2005 ][ 2005 ];
int main() {
cin >> n >> m;
for ( int i = 1; i <= m; i++ ) {
for ( int j = 1; j <= n; j++ ) {
cin >> arr[ i ][ j ];
}
}
/*
dp[i][j] 表示 前i组完成前j步最少使用的天数
从本组上一步来的 dp[i][j-1]
从上一组的上一步来的 dp[i-1][j-1]
dp[i][j] = min(dp[i][j-1], dp[(i-1+m)%m+1][j-1]) + arr[i][j];
*/
for ( int i = 1; i <= n; i++ ) dp[ 1 ][ i ] = arr[ 1 ][ i ];
for ( int k = 1; k <= 2; k++ ) {
for ( int i = 2; i <= m + 1; i++ ) {
int temp = i <= m ? i : 1;
for ( int j = 1; j <= n; j++ ) {
dp[ temp ][ j ] =
min( dp[ temp ][ j - 1 ], dp[ i - 1 ][ j - 1 ] ) + arr[ temp ][ j ];
}
}
}
// cout << "-------------------------" << endl;
long long minx = INF;
for ( int i = 1; i <= m; i++ ) {
minx = min( dp[ i ][ n ], minx );
}
cout << minx;
}