演算法›Ch3 動態規劃
第 40 題/共 40 題
◀ AL 40/40
40. Dynamic Programming
#AL-03-040中Dynamic Programming

(13%) You are going on a long hiking trip. You start on the road at kilometer post 0. Along the way there are n hotels, at kilometer posts a1<a2<⋯<ana_1 < a_2 < \cdots < a_n, where each aia_i is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance ana_n), which is your destination. You'd ideally like to travel 20 kilometers a day, but this may not be possible. If you travel x kilometers during a day, the penalty for that day is (20−x)2(20-x)^2. You want to plan your trip so as to minimize the total penalty. Give an algorithm that determines the optimal sequence of hotels at which to stop. (Note: This problem can be solved by a dynamic programming algorithm. If you use a dynamic programming algorithm to solve this problem, please write down the recursive formula of the algorithm, describe the meaning of the notations you used in the formula, give the initial value settings, and analyze the time complexity of the algorithm.)

📄 中央111
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃
本章題號 · 21–40 / 40