数字三角形WriteUp

题目:

题目链接:898. 数字三角形 - AcWing题库

题目截图:

image-20210114143611505

YXC AC源代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n;
int f[N][N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
cin >> f[i][j];
for (int i = n - 1; i; i -- )
for (int j = 1; j <= i; j ++ )
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
cout << f[1][1] << endl;

return 0;
}

Lxxx AC源代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
#include <algorithm>

const int N=510;
using namespace std;
int f[N][N];

int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> f[i][j];
}
}

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

cout << f[1][1] << endl;

return 0;
}

题目分析(DP 动态规划):

OI坐标轴与数学坐标轴的区别如下图所示:

image-20210114150043638

利用闫氏DP分析法如下:

由于这道题,从上至下考虑需要加一些特判,而从下至上考虑就不需要。

因此这道题采用从下至上的思路。

image-20210114150912806

其中f(i,j)表示从下至上走的所有路线的集合

这里的f(i,j)的属性,根据题目,属性值为最大值

假设w(i,j)表示处于(i,j)位置的数字

则,利用闫氏DP分析法可以得出下方表达式

image-20210114151537820

代码编写:

以下是原代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstring>
#include <algorithm>

const int N=510;
using namespace std;
int w[N][N],f[N][N];

int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> w[i][j];
}
}

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

for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);
}
}
cout << f[1][1] << endl;


return 0;
}

合并f,w数组,将下方代码进行等价变形

image-20210114152219028

变形之后的代码如下:

image-20210114152328349

最后整理之后的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
#include <algorithm>

const int N=510;
using namespace std;
int f[N][N];

int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> f[i][j];
}
}

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

cout << f[1][1] << endl;

return 0;
}

参考文章: