swift - 使用 Swift 4 对 NON-PRIME 数字进行三角求和

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>91 + 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

这是一个典型的问题，可以用 “dynamic programming” 解决。 : 这个想法是计算每个开始的最大可能总和金字塔中的点。

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

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

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])