题目

数字三角形 要求走到最后的和mod  100最大

每个数只能通过连线从上往下走

输入

第1行n，表示n行  < =25 第2到n+1行为每个的权值

输出

mod  100最大值

样例

样例输入1

2 1 99 98

样例输出1

99

评测结果

13个测试点，共对了7个点

代码

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;

const int N = 2e3 + 10;

int mp[N][N], d[N][N];

signed main()
{
	int n;
	cin >> n ;
	for(int i = 1; i <= n; ++ i)
	{
		for(int j = 1; j <= i; ++ j)
		{
			cin >> mp[i][j] ;
		}
	} 
	for(int i = 1; i <= n; ++ i)
	{
		for(int j = 1; j <= i; ++ j)
		{
			d[i][j] = max(d[i - 1][j - 1] + mp[i][j] % 100, d[i - 1][j] + mp[i][j] % 100);
		}
	}
	int ans = 0; 
	for(int i = 1; i <= n; ++ i)
	{
		// cout << d[n][i] << " " ;
		ans = max(ans, d[n][i] % 100);
	}
	cout << ans ;
	return 0;
}

大体思路

递推，递推式为 $d[i][j] = max(d[i - 1][j - 1] + mp[i][j]$，最后再遍历二维数组（矩阵）的最后一行取最大值（中间已经对100取模）

某位大佬的回复

感觉有点没听懂

希望大佬们能给出详细的解释