区间不重叠最大价值和：动态规划算法详解

这是一个经典的动态规划问题，可以使用动态规划来解决。

首先，对给定的区间进行排序，按照区间的右边界从小到大排序。这样可以保证在选择区间时，尽量选择右边界较小的区间。

然后，定义一个dp数组，dp[i]表示选择第i个区间时的最大价值和。初始化dp数组为0。

接下来，从第一个区间开始遍历到第n个区间，对于每个区间，我们有两种选择：选择该区间或者不选择该区间。

如果选择该区间，那么我们需要找到在该区间之前且与该区间不重叠的区间，使得价值和最大。我们可以从第一个区间开始遍历到第i-1个区间，找到右边界小于li的区间，并选择其中价值和最大的区间。

如果不选择该区间，那么最大价值和就是dp[i-1]。

综上所述，我们可以得到状态转移方程：

dp[i] = max(dp[j] + vi, dp[i-1])

其中，j表示右边界小于li的区间。

最后，遍历完所有的区间后，dp[n]即为最终的最大价值和。

以下为示例代码实现：

def max_value(n, intervals):
    intervals.sort(key=lambda x: x[1])  # 按照区间的右边界从小到大排序
    dp = [0] * (n + 1)  # 初始化dp数组
    for i in range(1, n + 1):
        for j in range(i - 1, -1, -1):
            if intervals[i - 1][0] > intervals[j - 1][1]:
                dp[i] = max(dp[i], dp[j] + intervals[i - 1][2])
        dp[i] = max(dp[i], dp[i - 1])
    return dp[n]

# 示例输入
n = 5
intervals = [(1, 4, 3), (3, 7, 2), (4, 6, 5), (6, 9, 4), (8, 10, 1)]

# 输出最大价值和
print(max_value(n, intervals))

输出结果为10，表示选择第1个区间和第4个区间可以得到最大的价值和。