关于边界问题的思考

这个代码和y总的课程代码不一样，因为写的时候我是从i=0，j=0开始写的，状态转移方程当然一样，但是边界考虑就很不一样了。

最开始初始化当i=0,j=0时有如下代码：

for(int i = 0;i<n;i++)
{
    for(int j = 0;j<=i;j++)
    {
        f[i][j] = -INF;
    }
}

应该注意到状态转移方程的f[i-1][j-1]，f[i][j-1]中的j，当j = 0时，得到的是f[i-1][-1]和f[i][-1]的值。

而我们定义的f[n][n]是全局变量，则f[0~n-1][-1] = 0
所以导致了在数据五中有负数的时候会WA掉。

所以我们应该这样初始化：

    for(int i = -1;i<n;i++)
    {
        for(int j = -1;j<=i+1;j++)
        {
            f[i][j] = -INF;
        }
    }

打卡代码：

#include<iostream>
using namespace std;

const int N  = 510;

int n;
int a[N][N];
int f[N][N];
const int INF = 1e9;
int main()
{
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<=i;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i = -1;i<n;i++)
    {
        for(int j = -1;j<=i+1;j++)
        {
            f[i][j] = -INF;
        }
    }

    f[0][0] = a[0][0];
    for(int i = 1;i<n;i++)
    {
        for(int j = 0;j<=i;j++)
        {
            f[i][j] = max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
        }
    }
    int ans = -INF;
    for(int i = 0;i<n;i++)
    {
        ans = max(f[n-1][i],ans);
    }
    cout<<ans;
}