动态规划-思考解决同一类问题的方式

题意：
nn正方形网格；
从左上角进，右下角出来，每穿一个小方格都需要花费一单位时间；
必须在（2n-1）个单位时间穿越出去。
中间每穿一个都需要交一定的费用。
请问至少交多少费用？

思考：
对于第一个条件：
2*n-1个时间单位

比如 3*3：

1 2 1
1 2 3
1 2 3

时间不超过 2*n-1，必须不走回头路；

思路：
摘花生->
动态规划问题就是这样,我们做题目时候,基本百分之八十的代码是重复的.
对于动态规划的问题,我们最好就是懂得所有动态规划DP的形式,他们是怎么DP出来的,所有类型的题目都做过后,我们菜可以通过经验去想出DP方程式,对,动态规划就是需要通过以有的大量经验去类推新的公式.

这个题目于这个对比
新的思考
边界问题；
i == 1 && j ==1 的时候初始；
i>1可以从左边过来
j>1可以从上面过来

#include <bits/stdc++.h>
#define pb(a) push_back(a)
#define pf push_front
#define beg begin
#define rb rbegin0
#define re rend
#define nd cout<<endl
#define all(s) s.begin(),s.end()
#define pi acos(-1.0)
#define MaxN 0x3f3f3f3f
#define MinN 0xc0c0c0c0
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=1e3+15;
const int inf=1e9;
int n;
int dp[N][N];
int w[N][N];
int main()
{
   
    while(cin>>n)
    {
   
       // memset(dp,0,sizeof(dp));
        for( int i=1; i<=n; i++)
        {
   
            for(int j=1; j<=n; j++)
            {
   
                cin>>w[i][j];
            }
        }
        for(int i=1; i<=n; i++)
        {
   
            for(int j=1; j<=n; j++)
            {
   
                if(i==1&&j==1)
                    dp[i][j]=w[1][1];
                else
                {
   
                    dp[i][j]=inf;
                    if(i>1)
                        dp[i][j]=min(dp[i][j],dp[i-1][j]+w[i][j]);
                    if(j>1)
                        dp[i][j]=min(dp[i][j],dp[i][j-1]+w[i][j]);
                }
            }
        }
        cout<<dp[n][n]<<endl;
    }
    return 0;
}