$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

结论： $f[i][j]=\min(f[i-1][j],\ f[i][j-1])+w[i][j]$

思路：

• $1. 状态表示$
  $集合：从\ (1,1)\ 走到\ (i,j)\ 的所有路线$
  $属性：\min$

• $2. 状态转移$
  $从\ (i,j)\ 上方走来：f[i][j]=f[i-1][j]+w[i][j]$
  $从\ (i,j)\ 左方走来：f[i][j]=f[i][j-1]+w[i][j]$

• $3. 滚动数组$
  $由于\ f[i][j]\ 只需用到当前层和上一层，则结论可转化为：f[j]=\min(f[j],\ f[j-1])+w[i][j]$

可参考： 摘花生

完整代码1

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int w[N][N];
int f[N][N]; //从 (1,1) 走到 (i,j) 的所有路线的最小值

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>w[i][j];

    //因为求最小值，所以需要初始化为正无穷
    memset(f,0x3f,sizeof f);
    f[1][1]=w[1][1];

    for(int i=1;i<=n;i++)   
        for(int j=1;j<=n;j++)
            if(i!=1||j!=1)
                f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];

    cout<<f[n][n]<<endl; //从 (1,1) 走到 (n,n) 的所有路线的最小值

    return 0;
}

完整代码2

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int w[N][N];
int f[N]; //从 (1,1) 走到 (i,j) 的所有路线的最小值

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>w[i][j];

    //因为求最小值，所以需要初始化为正无穷
    memset(f,0x3f,sizeof f);
    f[1]=w[1][1];

    for(int i=1;i<=n;i++)   
        for(int j=1;j<=n;j++) //保证了 f[j-1] 是 f[i][j-1]
            if(i!=1||j!=1)
                f[j]=min(f[j],f[j-1])+w[i][j];

    cout<<f[n]<<endl; //从 (1,1) 走到 (n,n) 的所有路线的最小值

    return 0;
}