# How can I generate path according to lexicograpical ordering for this solution structure? (expect that it should be doable with this structure)

• I wrote the following code during the contest time duration. It uses cost[k] to store the best cost from index 1 to K+1, and uses DP (top-down, in the form of recursion with memoization using cost[] vector). The 'best' and 'bestj' variables in findPath are used to store the best cost when comparing among the i-1, i-2,...i-B for an index i.

This program doesn't seem to produce path output for the lexicographical ordering rule, and gives wrong answer for the following case.

``````Input:[0,0,0,0,0,0]
3
Output:[1,3,6]
Expected:[1,2,3,4,5,6]
``````

Can someone explain how I can make this work for the lexicographical ordering rule? Most explanations in this forum have DP[K] storing the cost for K+1... to N the index, so that doesn't directly apply. How can I make the way this solution is constructed produce also path per the lexicographical ordering?

``````class Solution {
public:
vector<int> cheapestJump(vector<int>& A, int B) {
vector<int> path;
vector<int> cost(A.size(), INT_MAX);
path.emplace_back(1);
cost[0] = A[0];
findPath(A, B, cost, path, A.size()-1);

if (A[A.size()-1] != -1)
path.emplace_back(A.size());
else
path.clear();
return path;
}

void findPath(vector<int>& A, int B, vector<int>& cost, vector<int>&path, int idx) {
if (idx == 0) return;
int best = INT_MAX;
int bestj = -1;
for (int i=1; i<=B && idx-i >=0 && A[idx] != -1; i++) {
int j = idx-i;
if (A[j] == -1) continue;
if (cost[j] == INT_MAX) {
findPath(A, B, cost, path, j);
path.pop_back();
}
if (cost[j] == INT_MAX) {
A[j] = -1;
continue;
}
int tmp = cost[j] + A[idx];

if (tmp <= best) {
best = tmp;
bestj = j;
}
}
cout << idx << " ::: " << best << " ::: " << bestj << endl;
if (bestj != -1) {
cost[idx]= best;
path.emplace_back(bestj+1);
}
else
A[idx] = -1;
}

};
``````

• o that doesn't dir

I had the same issue as well, I couldn't find a way, let me know once you do.

• @venkata-sai-krishn same issue here for this test case. Would love to know how you solved it. Thanks!

• Hey @edaengineer same issue here.
I was wondering whether we are wrong to " store the best cost from index 1 to K+1"?
Still stuck in this question, love to hear your advice ! Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.