三角形 用 Swift 4 用非素数向下求和

Question

我知道这个问题之前针对不同的编程语言被问过，我试图用 Swift 4 实现这个问题，但是一旦我提交答案，我被告知我的答案是错误的，所以这是任务;

您将从文件中输入一个三角形，您需要根据以下给定规则找到数字的最大总和;

1. 您将从顶部开始，向下移动到相邻的数字，如下所示。
2. 您只能向下和对角线行走。
3. 你只能走过非质数。

根据上述规则，以下示例中从上到下的最大数字总和为 24。

var sampleString = """
1
8  4
2  6  9
8  5  9  3

如您所见，这有几条路径符合非素数的规则; 1>8>6>9， 1>4>6>9， 1>4>9>9 1 + 8 + 6 + 9 = 24。 如您所见，1、8、6、9 都不是素数，走过这些数字会产生最大总和。

赋值字符串：

var assignmentString = """
215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 53  627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233"""

我的代码：

func maxSumForTriangle(triangleString: String) {
var temporaryIndex = 0
var earlierIndex = 0
var greatSum = 0
var temporaryMaxInLine = 0
let values = triangleString.components(separatedBy: .newlines).map {
$0.components(separatedBy: .whitespaces).compactMap(Int.init)
}
print(values)
print(values.count)
for line in values {
if line.count == 1 {
greatSum += line[0]
earlierIndex = line.count - 1
} else {
for number in line.enumerated() {
if number.offset == earlierIndex || number.offset == earlierIndex + 1 {
//Check the number if its prime or not with the isPrime function we defined
if !isPrime(number.element) {
if number.element > temporaryMaxInLine {
temporaryMaxInLine = number.element
temporaryIndex = number.offset
}
}
}
}
earlierIndex = temporaryIndex
greatSum += temporaryMaxInLine
temporaryMaxInLine = 0
}
}
print(greatSum)
}

这导致了 7619，但后来我意识到我的问题在哪里;我不会检查每条可能的路径，我只是检查每行的最高非素数并继续求和。

所以我需要为这个问题找到一种不同的方法，以便我的函数可以检查每个可能的情况并以最高总和返回

我还想不通，我是否应该实现一个不同的函数，让它再次调用自己，以便它可以检查所有可能的路径？

很抱歉这个问题很长，但我也想展示我的旧实现。

Answer 1

这是一个典型的问题，可以用"动态规划"来解决： 是计算每个起始的最大可能总和 金字塔中的点。

如果我们从底行开始向上工作，这变得很简单： 我们只需要将两个较低邻居中较大的一个添加到每个条目中。 最后，顶部条目是所需的最大总和。

考虑到关于非素数的附加条件，这 可以实现为

var values = triangleString.components(separatedBy: .newlines).map {
$0.components(separatedBy: .whitespaces).compactMap(Int.init)
}
for row in values.indices.reversed() {
for col in values[row].indices {
if isPrime(values[row][col]) {
values[row][col] = Int.min
} else if row + 1 < values.endIndex {
values[row][col] += max(values[row+1][col], values[row+1][col+1])
}
}
}
print(values[0][0])