C++动态规划引入数字三角形

Question

原题洛谷：https://www.luogu.com.cn/problem/P1216
照葫芦画瓢第一次写的DP，但是只通过了2/9，不知道哪里有问题，请求指导

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int dp_function(int n){
    int arr[1001][1001];
    int dp[1001][1001];   //dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+arr[i][j]//request=dp[n-1][n-1]
    for(int i=0;i<5;i++){
        for(int j=0;j<=i;j++){
        scanf("%d",&arr[i][j]);
        if(i==0)dp[i][j]=arr[i][j];
        if(j==0)dp[i][j]=dp[i-1][j]+arr[i][j];
        }
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+arr[i][j];
        }
    }
    return dp[n-1][n-1];
}

int main(){
    int n;
    //dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+dp[i][j]//request=dp[n-1][n-1]
    scanf("%d",&n);
    printf("%d",dp_function(n));
    return 0;
} 

Answer 1

• 数组越界
  你的二维数组定义为 int arr[1001][1001]，但是只读入了5行数字，所以当n大于5时，数组会越界。正确的定义应该是 int arr[1001][1001] = {0}，这样数组中的所有元素都会初始化为0，可以避免数组越界问题。

• 贪心算法错误
  你的dp转移方程为 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+arr[i][j]，这是贪心算法的思想，但是这个思想在本题中不适用。因为你要求的是从顶部到底部的最大路径和，但是这个路径上的数并不一定是每一行中的最大值。例如，在样例中，第1行的5是最大值，但是最大路径和的路径是 7->6->9->3->2，其中第1行的5并没有被选中。

• 变量重复定义
  你在dp_function函数中定义了一个变量 dp，但是这个变量和外面的变量名相同，会导致变量重复定义的错误。建议将内部变量的名称更改为 dpArr。