LeetCode 1548. The Most Similar Path in a Graph（动态规划）
文章目錄
- 1. 題目
- 2. 解題
1. 題目
We have n cities and m bi-directional roads where roads[i] = [ai, bi] connects city ai with city bi. Each city has a name consisting of exactly 3 upper-case English letters given in the string array names. Starting at any city x, you can reach any city y where y != x (i.e. the cities and the roads are forming an undirected connected graph).
You will be given a string array targetPath. You should find a path in the graph of the same length and with the minimum edit distance to targetPath.
You need to return the order of the nodes in the path with the minimum edit distance, The path should be of the same length of targetPath and should be valid (i.e. there should be a direct road between ans[i] and ans[i + 1]). If there are multiple answers return any one of them.
The edit distance is defined as follows:
Follow-up: If each node can be visited only once in the path, What should you change in your solution?
Example 1:
Example 2:
Example 3:
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/the-most-similar-path-in-a-graph
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
class Solution { public:vector<int> mostSimilar(int n, vector<vector<int>>& roads, vector<string>& names, vector<string>& targetPath) {vector<vector<int>> g(n);for(auto& r : roads){g[r[0]].push_back(r[1]);g[r[1]].push_back(r[0]);}//建圖int len = targetPath.size();vector<vector<int>> dp(len, vector<int>(n, INT_MAX));//走完 ？target后的 在城市 ni 的最小編輯距離vector<vector<int>> path1(n);//n個城市作為結束的最佳路線vector<vector<int>> path2(n);//存儲下一個狀態的路徑for(int i = 0; i < n; ++i)//初始化{dp[0][i] = (names[i] != targetPath[0]);path1[i].push_back(i);}int mindis = INT_MAX, minidx = -1;for(int k = 1; k < len; ++k){ //樣本維度for(int i = 0; i < n; ++i){ //前一個城市if(dp[k-1][i] == INT_MAX)continue;for(int j : g[i]){ //下一個相連的城市if(dp[k][j] > dp[k-1][i]+(names[j]!=targetPath[k])){dp[k][j] = dp[k-1][i]+(names[j]!=targetPath[k]);path2[j] = path1[i];path2[j].push_back(j);}}}swap(path1, path2);//滾動數組，更新當前的最佳路徑至path1}for(int i = 0; i < n; i++) {if(mindis > dp[len-1][i]){mindis = dp[len-1][i];minidx = i;}}//取編輯距離最小的城市編號return path1[minidx];//返回路徑} };1260 ms 109.6 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 1548. The Most Similar Path in a Graph（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： LeetCode MySQL 1398.
- 下一篇： LeetCode 1750. 删除字符串