这是意义非凡的18题：
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.
2018-01-28_182813.png
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
mark
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)
这个问题就是很逗，他不准你用遍历的方法，说是有16384种，这个数字哪来的呢？因为每一次都是2个选择，总共要做14次选择
2^14=16384
即使用了遍历的方法，那么对于第67题，有100层，也就是2^99次方。
只要是听过棋盘里面放谷子那个故事的人就知道2^64有多大。
为了准确地知道2^99有多大，第67题给了个例子：
假如我们1秒钟能够检测1万亿条路径，大概需要200亿年才能检测完。
所以这题的算法比算力重要的多。
我想了半天都没有想出什么结果，甚至我都不知道如何才能把那个三角形的数字给导入R语言，
一开始我是这么弄的：
a01 <- c(75)
a02 <- c(95,64)
a03 <- c(17,47,82)
a04 <- c(18,35,87,10)
a05 <- c(20,04,82,47,65)
a06 <- c(19,01,23,75,03,34)
a07 <- c(88,02,77,73,07,63,67)
a08 <- c(99,65,04,28,06,16,70,92)
a09 <- c(41,41,26,56,83,40,80,70,33)
a10 <- c(41,48,72,33,47,32,37,16,94,29)
a11 <- c(53,71,44,65,25,43,91,52,97,51,14)
a12 <- c(70,11,33,28,77,73,17,78,39,68,17,57)
a13 <- c(91,71,52,38,17,14,91,43,58,50,27,29,48)
a14 <- c(63,66,04,68,89,53,67,30,73,16,69,87,40,31)
a15 <- c(04,62,98,27,23,09,70,98,73,93,38,53,60,04,23)
思前想后，还是搞不定，当时我想，这个要断更了。
求助网络后，我发现一种奇特的解法。
复制粘贴三角形数字保存为chart.txt
read.table读入R语言并且转换成矩阵
n <- 15
chart <- read.table("chart.txt", sep = " ", fill = NA, col.names = 1:n)
chart <- as.matrix(chart)
查看一下chart是这个样子的：
mark
下面的思路特别精彩：
第一个数是75，他向下可以到95，也可以到64
那么第二行如果写成和的形式就是75+95=170，75+64=139
对于第三行而言，有三个数，第一个数只能来自于上一行的第1个数，最后一个数只能是来源于上一行的最后一个数。
变数实际上是第二个数，他可以有两个来源，他一从170过来，也可以从139过来，这里当然选择最大的170+47=217,
所以前三行已经变成了这个样子：
> chart
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15
[1,] 75 NA NA NA NA NA NA NA NA NA NA NA NA NA NA
[2,] 170 139 NA NA NA NA NA NA NA NA NA NA NA NA NA
[3,] 187 217 221 NA NA NA NA NA NA NA NA NA NA NA NA
顺着这个思路，每一行的头尾数都没有争议，有选择的是中间的每一个数，他们都有两个可能性，我们选取他们中的最大值。
chart[2, 1:2] <- chart[2, 1:2] + chart[1, 1]
for (i in 3:n) {
chart[i, 1] <- chart[i, 1] + chart[(i - 1), 1]
chart[i, i] <- chart[i, i] + chart[(i - 1), (i - 1)]
for (j in 2:(i - 1)) {
chart[i, j] <- chart[i, j] + max(chart[(i - 1), (j - 1):j])
}
}
最终最大值可以在最后一行中找出：
> result <- max(chart[n, ])
> cat("The result is:", result, "\n")
The result is: 1074
好的，我们用这个方法去解答第67题：
n <- 100
chart <- read.table("chart.txt", sep = " ", fill = NA, col.names = 1:n)
chart <- as.matrix(chart)
chart[2, 1:2] <- chart[2, 1:2] + chart[1, 1]
for (i in 3:n) {
chart[i, 1] <- chart[i, 1] + chart[(i - 1), 1]
chart[i, i] <- chart[i, i] + chart[(i - 1), (i - 1)]
for (j in 2:(i - 1)) {
chart[i, j] <- chart[i, j] + max(chart[(i - 1), (j - 1):j])
}
}
答案几乎是秒出：
> result <- max(chart[n, ])
> cat("The result is:", result, "\n")
The result is: 7273
换种思路，让不可能变成可能，让200亿年缩成1s，甚至做完题我都有种荡气回肠的感觉。
思维是我们超越时间的最强武器。
网友评论