1 条题解
-
0
道题是一道经典的动态规划问题,可以使用动态规划的思想来解决。以下是可能的算法流程:
- 定义一个二维数组
dp[i][j]
,其中dp[i][j]
表示到达第i
行第j
列时所能得到的最大珠宝数目。 - 初始化第一行的值,即
dp[0][0] = a[0][0]
,对于第一行的其他列,有dp[0][j] = dp[0][j-1] + a[0][j]
。 - 对于第
i
行(1 <= i < n),根据它的上一行i-1
的结果,递推计算dp[i][j]
的值。具体地,有以下两种情况:- 如果
j == 0
,即当前行的第一列,有dp[i][j] = dp[i-1][j] + a[i][j]
。 - 如果
j > 0
,即当前行的其他列,有dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
。
- 如果
- 最终的答案是
max(dp[n-1][0], dp[n-1][1], ..., dp[n-1][n-1])
。
以下是参考代码
#include <iostream> #include <algorithm> using namespace std; const int MAXN = 105; // 最大行数 int a[MAXN][MAXN]; // 存储每行的珠宝数目 int dp[MAXN][MAXN]; // dp[i][j] 表示到达第 i 行第 j 列时所能得到的最大珠宝数目 int main() { int n; cin >> n; // 读入每行的珠宝数目 for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { cin >> a[i][j]; } } // 初始化第一行的值 dp[0][0] = a[0][0]; for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j-1] + a[0][j]; } // 递推计算 dp[i][j] 的值 for (int i = 1; i < n; i++) { for (int j = 0; j <= i; j++) { if (j == 0) { dp[i][j] = dp[i-1][j] + a[i][j]; } else { dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]; } } } // 找出最大值 int ans = dp[n-1][0]; for (int j = 1; j < n; j++) { ans = max(ans, dp[n-1][j]); } cout << ans << endl; return 0; }
- 定义一个二维数组
- 1
信息
- ID
- 1020
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者