Part II: Non Multiple Choice questions (非選擇題)

1. (10%). You are given a directed acyclic graph $G = (V,E)$ with real-valued edge weights and two distinguished vertices $s, t \in V$. The weight of a path is the sum of the weights of the edges in the path.

(a) Describe a dynamic-programming approach for finding a simple path from $s$ to $t$ with the maximum weight. Write down the recurrence formula you use and the definition of the subproblem(s) explicitly.

(b) What is the running time of your algorithm?