每日算法 金字塔型线性动态规划

顺序推断（用 for 循环并且把每次的结果记录下来，方便计算）

package main

import (
    "fmt"
)

// Function to find the maximum path sum in a triangle using forward dynamic programming
func maximumPathSum(triangle [][]int) int {
    n := len(triangle) // Number of rows in the triangle

    // Create a DP table with the same dimensions as the triangle
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, len(triangle[i]))
    }

    // Initialize the top element
    dp[0][0] = triangle[0][0]

    // Fill the DP table from top to bottom
    for i := 1; i < n; i++ { // Start from the second row
        for j := 0; j < len(triangle[i]); j++ {
            if j == 0 {
                // First element in the row can only come from the first element of the previous row
                dp[i][j] = triangle[i][j] + dp[i-1][j]
            } else if j == len(triangle[i])-1 {
                // Last element in the row can only come from the last element of the previous row
                dp[i][j] = triangle[i][j] + dp[i-1][j-1]
            } else {
                // Middle elements can come from either of the two elements above
                dp[i][j] = triangle[i][j] + max(dp[i-1][j], dp[i-1][j-1])
            }
        }
    }

    // Find the maximum path sum in the last row
    maxSum := dp[n-1][0]
    for _, val := range dp[n-1] {
        if val > maxSum {
            maxSum = val
        }
    }

    return maxSum
}

// Helper function to find the maximum of two integers
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    // Example triangle
    triangle := [][]int{
        {3},
        {7, 4},
        {2, 4, 6},
        {8, 5, 9, 3},
    }

    // Calculate the maximum path sum
    maxSum := maximumPathSum(triangle)

    // Print the result
    fmt.Printf("The maximum path sum is: %d\n", maxSum)
}

[
  [3],
  [7, 4],
  [2, 4, 6],
  [8, 5, 9, 3]
]

解题过程（顺序推解）

1. 初始化：

   • dp[0][0] = triangle[0][0] = 3

2. 从第二行开始逐层计算：

   • 第二行：

     dp[1][0] = triangle[1][0] + dp[0][0] = 7 + 3 = 10
     dp[1][1] = triangle[1][1] + dp[0][0] = 4 + 3 = 7

   • 第三行：

     dp[2][0] = triangle[2][0] + dp[1][0] = 2 + 10 = 12
     dp[2][1] = triangle[2][1] + max(dp[1][0], dp[1][1]) = 4 + max(10, 7) = 14
     dp[2][2] = triangle[2][2] + dp[1][1] = 6 + 7 = 13

   • 第四行：

     dp[3][0] = triangle[3][0] + dp[2][0] = 8 + 12 = 20
     dp[3][1] = triangle[3][1] + max(dp[2][0], dp[2][1]) = 5 + max(12, 14) = 19
     dp[3][2] = triangle[3][2] + max(dp[2][1], dp[2][2]) = 9 + max(14, 13) = 23
     dp[3][3] = triangle[3][3] + dp[2][2] = 3 + 13 = 16

3. 最终结果：

   • 最后一行的最大值为 max(20, 19, 23, 16) = 23
   • 因此，从顶部到底部的最大路径和为 23。

逆序推断（递归，但是需要先遍历到最低再回溯）

package main

import (
    "fmt"
    "math"
)

// Function to find the maximum path sum in a triangle using recursion
func maximumPathSum(triangle [][]int, row, col int) int {
    // Base case: if we reach the bottom row, return the value of the current element
    if row == len(triangle)-1 {
        return triangle[row][col]
    }

    // Recursive case: calculate the maximum path sum for the two adjacent elements in the next row
    leftSum := maximumPathSum(triangle, row+1, col)
    rightSum := maximumPathSum(triangle, row+1, col+1)

    // Return the maximum path sum for the current element
    return triangle[row][col] + max(leftSum, rightSum))
}

func main() {
    // Example triangle
    triangle := [][]int{
        {3},
        {7, 4},
        {2, 4, 6},
        {8, 5, 9, 3},
    }

    // Calculate the maximum path sum starting from the top
    maxSum := maximumPathSum(triangle, 0, 0)

    // Print the result
    fmt.Printf("The maximum path sum is: %d\n", maxSum)
}

逆序就是通过回溯计算子问题，并且将子问题聚合成大一点的子问题，最终聚合成题目所需的大问题。

解题过程（递归）

1. 基本情况：

   • 当 row = 3 时，直接返回 triangle[3][col] 的值。

2. 递归步骤：

   • 从 row = 2 开始，递归地计算每个节点的最大路径和：

     • dp[2][0] = triangle[2][0] + max(maximumPathSum(3, 0), maximumPathSum(3, 1)) = 2 + max(8, 5) = 10
     • dp[2][1] = triangle[2][1] + max(maximumPathSum(3, 1), maximumPathSum(3, 2)) = 4 + max(5, 9) = 13
     • dp[2][2] = triangle[2][2] + max(maximumPathSum(3, 2), maximumPathSum(3, 3)) = 6 + max(9, 3) = 15

   • 从 row = 1 开始，递归地计算每个节点的最大路径和：

     • dp[1][0] = triangle[1][0] + max(maximumPathSum(2, 0), maximumPathSum(2, 1)) = 7 + max(10, 13) = 20
     • dp[1][1] = triangle[1][1] + max(maximumPathSum(2, 1), maximumPathSum(2, 2)) = 4 + max(13, 15) = 19

   • 从 row = 0 开始，递归地计算每个节点的最大路径和：

     • dp[0][0] = triangle[0][0] + max(maximumPathSum(1, 0), maximumPathSum(1, 1)) = 3 + max(20, 19) = 23

3. 最终结果：

   • 从顶部到底部的最大路径和为 23。

这里也可以看出，回溯和递归其实就是看在进入方法前做事还是进入方法后做事，进入方法后做事就是回溯的范围，进入方法前做事就是正常递归的范围。

总结

上面的为我学习的一些代码示例和题目示例，这题能很好的展现出顺序方式动态规划的状态和状态转移相关的内容。