Project Euler 18

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

Project Euler 18

题目

Maximum path sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is \(23\).
3
7 4
2 4 6
8 5 9 3

That is, \(3 + 7 + 4 + 9 = 23\).

Find the maximum total from top to bottom of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only \(16384\) routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

解决方案

将数字三角形直接转化成一个以左下角为顶点的直角三角形，存在p018.txt中，方便读取：

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

此时可以将问题转化为：要么向下走，要么向右下角走。

本题将用到动态规划算法。

令\(n=15\)，其中\(n\)表示数字三角形的大小，记录状态\(f(i,j)(1\leq j\leq i\leq n)\)为：当前走到第\(i\)行第\(j\)列的数的情况下，可以得到的路径最大和是多少，用\(a[i][j]\)表示第\(i\)行第\(j\)列的数。

那么，可以得到状态转移方程：

\[ f(i,j)= \left \{\begin{aligned} &a[i][j] & & \text{if}\quad i=j=1 \\ &f(i-1,j-1)+a[i][j] & & \text{else if}\quad j=i \\ &f(i-1,j)+a[i][j] & & \text{else if}\quad j=1 \\ &\max(f(i-1,j-1),f(i-1,j)) + a[i][j] & & \text{else} \end{aligned}\right. \]

最后的答案则是\(\max_{j=1}^n\{f(n,j)\}\).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# include <bits/stdc++.h>
using namespace std;
const int N=15;
int t,f[N+4][N+4];
int main(){
    freopen("p018.txt","r",stdin);
    for(int i=1;i<=N;i++)
    for(int j=1;j<=i;j++){
        scanf("%d",&t);
        f[i][j]=max(f[i-1][j-1],f[i-1][j])+t;
    }
    int ans=*max_element(f[N]+1,f[N]+N+1);
    printf("%d\n",ans);
}