牛妹的野菜
先把路径可行的转化成01矩阵的形式做一下预处理,方便后面
使用dp[]记录以这个点为终点的最多番薯数量
枚举所有两两相连的路径,更新dp,边更新边记录连接关系c[i]=j,表示j->i有最优的路径。
然后,逆流而上,找到头。输出~~
注意一个小坑是数组以0开始下标,输出和connectRoad都是1开始的记法呀
class Solution { public: /** * * @param potatoNum int整型vector 依次表示序号为1,2,3..的番薯洞各有多少个番薯 * @param connectRoad int整型vector<vector<>> 每个一维数组[x,y]表示从第x号番薯洞到第y号有路 * @return string字符串 */ string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) { // write code here int n = potatoNum.size(); vector<int>dp(n+1,0); dp[0] = 0; vector<int>c(n+1,0); vector<int>b(n+1,0); vector<vector<int> > x(n+1, vector<int>(n+1, 0)); for (int i = 1; i <= n; i ++) x[0][i] = 1; for (int i = 0; i < connectRoad.size(); i ++) { x[connectRoad[i][0]][connectRoad[i][1]] = 1; } for (int i = 1; i <= n; i ++) { for (int j = i-1; j >= 0; j --) { if (x[j][i] == 1 && dp[i] < dp[j] + potatoNum[i-1]) { c[i] = j; dp[i] = dp[j] + potatoNum[i-1]; } } } int kt = 0, mx = -999; for (int i = 1; i <= n; i ++) { if (mx < dp[i]) { mx = dp[i]; kt = i; } } int p = 0; while (kt != 0) { b[++p] = kt; kt = c[kt]; } string ans = ""; string spl = "-"; for (int i = p; i >= 1; i --) { ans += to_string(b[i]); if(i!=1) ans += spl; } return ans; } };