91影视

Dynamic programming helps to solve the problems that can be divided into subproblems and the solution of subproblems is used to calculate the optimal solution of the problem. Dynamic programming obtains both local and global optimal solution.

The objective of the algorithm is to reduce the penalty.

Consider $OP\left(i\right)$as the minimum total penalty to reach hotel $i$. Before reaching hotel $i$, keep the track of all hotels$j$ which can be used to stay. So, the minimum penalty to reach hotel$i$ is the sum of minimum penalty to reach hotel 鈥�$j鈥�$鈥� and the cost of trip from$j$ to$i$ is ${\left(200鈭�\left(a_j鈭�a_i\right)\right)}^2$.

Thus, $OP\left(i\right)=\text{MIN}\left(OP\left(j\right)+{\left(200鈭�\left(a_j鈭�a_i\right)\right)}^2\right)$.

The base value is $OP\left(0\right)=0$because$i=0$ is the starting point of the trip. Call the function recursively within the loop to get minimum penalty to reach hotel $n$.

The algorithm to find the optimal sequence of hotels is as follows:

$\begin{array}{l}OP\left(0\right)=0\\ \text{for}\left(i=0\text{鈥则辞鈥�}n\right)\\ \text{鈥勨赌勨赌�}OP\left(i\right)=\text{MIN}\left(OP\left(j\right)+{\left(200鈭�\left(a_j鈭�a_i\right)\right)}^2\right)\text{鈥刦辞谤鈥�}j=0\text{鈥则辞鈥�}i鈭�1\\ \text{谤别迟耻谤苍鈥�}OP\left(n\right)\end{array}$

Thus, the algorithm returns the minimum penalty