蓝桥杯备考：动态规划路径类DP之矩阵的最小路径和
如题，要求左上角到右下角的最短路径，我们还是老样子按顺序做
step1:确定状态表示 f[i][j]表示(1,1)到(i,j)的最短距离
step2 :推导状态表达方程
step3:确定填表顺序，应该是从上到下，从左到右
step4:初始化
step5 找结果，结果就存在f[n][m]这里
好的，我们直接来实现一下代码就行了
#include <iostream> #include <cstring> using namespace std; int n,m; const int N = 510; int f[N][N]; int main() { cin >> n >> m; memset(f,0x3f,sizeof f); f[0][1] = 0; for(int i = 1;i<=n;i++) { for(int j = 1;j<=m;j++) { int x; cin >> x; f[i][j] = min(f[i-1][j],f[i][j-1])+x; } } cout << f[n][m] << endl; }