day05 - PHP 实现 N 个村庄建立 M 个邮局，村庄距离邮局距离最短

思路已经理解了，但是代码部分还是有点问题，先记录到这里

 

class Solution { /** * @param Integer[] $nums * @return Integer */ function maxSubArray($nums) { // 从第 i 个村庄到 j 个村庄建立一个邮局 // dis[i][j] = dis[i][j-1] + a[j] - a[(i+j)/2]; $size = count($nums); $m = 5; $dis[1][1] = 0; for ($i = 1; $i <= $size; $i++) { for ($j = $i+1; $j <= $size; $j++) { $dis[$i][$j] = $dis[$i][$j-1] + abs($nums[$j] - $nums[floor(($i + $j)/2)]); } } for ($i = 1; $i <= $size; $i++) { $dp[$i][$i] = 0; $dp[$i][1] = $dis[1][$i]; } var_dump($dp); // dp[i][j] = min(dp[i][j],dp[k][j-1] + dis[k+1][i]) for ($j = 2; $j <= $m; $j++) { for ($i=$j + 1; $i <= $size; $i++) { for ($k = $i - 1; $k < $i; $k++) { $dp[$i][$j] = min($dp[$i][$j], $dp[$k][$j - 1] + $dis[$k+1][$i]); } } } } }