是否有一种算法可以在有向根树中找到最小代价路径（树状结构？）>

Question

更具体地说：我有一棵有根的树，它表示矩阵从其第一个元素到最后一个元素的不同路径，只允许向右，向下和对角向下移动。因此，每个节点最多可以有3个子节点。该树将以矩阵的第一个元素为根，每个最后一个节点将是矩阵的最后一个元素。每个节点代表一个成本。

这是我在谈论哪种树的示例：

这里的最小成本路径是：“ [坐标]中的1-> 2-> 9

或[0,0,2]

那么，有没有一种算法能够找到这种树的最小成本路径（我的意思是路径而不是最小成本路径的总成本）？如果是，是否可以以递归方式实现它？

更具体地说：我有一棵有根的树，它表示矩阵从其第一个元素到最后一个元素的不同路径，只允许向右，向下和对角向下移动。因此，每个...

Answer 1

这可以在O（n

）时间内完成，其中n