Leetcode 3149. Find the Minimum Cost Array Permutation

• Leetcode 3149. Find the Minimum Cost Array Permutation
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3149. Find the Minimum Cost Array Permutation

1. 解题思路

这一题的话就是一个动态规划的问题，不过他这个错位着实是把题目变得复杂了不少，唉……

思路上的话实在是没啥可多说的，整体来说就是动态规划加剪枝，唯一的问题就是细节实现上容易踩坑，这里就不一一赘述了，仅把代码放在下面，有兴趣的读者可以自行研究一下。

2. 代码实现

给出python代码实现如下：

class Solution:def findPermutation(self, nums: List[int]) -> List[int]:n = len(nums)status = 0best_score = math.inf@lru_cache(None)def dp(idx, status, first, pre, pre_score):nonlocal best_scoreif pre_score >= best_score:return math.inf, []if idx >= n:best_score = min(best_score, abs(pre - nums[first]) + pre_score)return abs(pre - nums[first]) + pre_score, []score, ans = math.inf, []for i in range(n):if status & (1 << i) == 0:if idx == 0:s, nxt = dp(idx+1, status | (1 << i), i, i, 0)else:s, nxt = dp(idx+1, status | (1 << i), first, i, pre_score + abs(pre-nums[i]))if s < score:ans = [i] + nxtscore = sreturn score, ansscore, ans = dp(0, 0, 0, 0, 0)return ans

提交代码评测得到：耗时7140ms，占用内存237.1MB。