787. K 站中转内最便宜的航班 | 514.自由之路

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

示例 1：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
示例 2：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

思路：动态规划 

注意边界判断和函数的返回值 

旅游省钱大法：加权最短路径 :: labuladong的算法小抄 (gitee.io)

class Solution {
public:unordered_map<int,vector<pair<int,int>>> indegree;int src;vector<vector<int>> memo;int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {memo.resize(n,vector<int>(k+2,-1000));this->src=src;for(auto& flight:flights)//存储每个结点的入度以及边的权值{int from=flight[0];int to=flight[1];int price=flight[2];indegree[to].emplace_back(from,price);}return dp(dst,k+1);}//dp函数定义：从src出发，在k步之内到达dst的最便宜的价钱int dp(int dst,int k){if(src==dst)//base casereturn 0;if(k<=0)//步数不够，无法到达return -1;if(memo[dst][k]!=-1000)//备忘录，减少重复计算return memo[dst][k];int res=INT_MAX;for(pair<int,int>& i:indegree[dst])//动态转移{int pre=i.first;int price=i.second;int subProblem=dp(i.first,k-1);if(subProblem!=-1)res=min(res,subProblem+price);}if(res!=INT_MAX)memo[dst][k]=res;else//res在此处仍为INT_MAX,说明dst的入度为0或者步数不足，两者都代表无法到达memo[dst][k]=-1;return memo[dst][k];}
};

 514.自由之路

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中：

您可以将 ring 顺时针或逆时针旋转 一个位置 ，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。
 

示例 1：

输入: ring = "godding", key = "gd"
输出: 4
解释:
 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。

示例 2:

输入: ring = "godding", key = "godding"
输出: 13

思路：动态规划 

动态规划帮我通关了《辐射4》 :: labuladong的算法小抄 (gitee.io) 

class Solution {
public:unordered_map<char,vector<int>> charToIndex;vector<vector<int>> memo;int findRotateSteps(string ring, string key) {memo.resize(ring.size(),vector<int>(key.size(),-1));for(int i=0;i<ring.size();i++){charToIndex[ring[i]].push_back(i);}return dp(ring,key,0,0);}//dp函数定义：指针指向ring[i]，拼出key[j..]所需的最少步数int dp(string& ring,string& key,int i,int j){if(j>=key.size())//base case{return 0;}int res=INT_MAX;if(memo[i][j]!=-1){return memo[i][j];}for(int k:charToIndex[key[j]])//key[j]在ring中可能对应着多个位置{int delta=abs(k-i);//因为ring.size()的返回值没有规定类型//所以ring.size()-delta的类型也就没有规定，和min函数参数类型不符，应该强制类型转换delta=min(delta,(int)(ring.size()-delta));//选择顺时针还是逆时针int subProblem=dp(ring,key,k,j+1);//将指针拨到ring[k]，拼出key[j+1..]的最小步数res=min(res,subProblem+delta+1);//加一是因为按下按钮也是一次操作}memo[i][j]=res;return res;}
};