C++, DP, O(nB) time O(n) space


  • 13
    Z

    This is a classic DP problem. dp[k] (starting from k = 0) is the minimum coins from Ak+1 to An, and pos[k] is the next place to jump from Ak+1.

    If working backward from dp[n-1] to dp[0], and considering smaller index first, i.e. i+1 to i+B, there is no need to worry about lexicographical order. I argue pos[k] always holds the lexicographically smallest path from k to n-1, i.e. from Ak+1 to An. The prove is as below.

    Clearly, when k = n-1, it is true because there is only 1 possible path, which is [n]. When k = i and i < n-1, we search for an index j, which has smallest cost or smallest j if the same cost. If there are >= 2 paths having the same minimum cost, for example,
    P = [k+1, j+1, ..., n]
    Q = [k+1, m+1, ..., n] (m > j)
    The path P with smaller index j is always the lexicographically smaller path.
    So the argument is true by induction.

    class Solution {
    public:
        vector<int> cheapestJump(vector<int>& A, int B) {
            vector<int> ans;
            if (A.empty() || A.back() == -1) return ans;
            int n = A.size();
            vector<int> dp(n, INT_MAX), pos(n, -1);
            dp[n-1] = A[n-1];
            // working backward
            for (int i = n-2; i >= 0; i--) {
                if (A[i] == -1) continue;
                for (int j = i+1; j <= min(i+B, n-1); j++) {
                    if (dp[j] == INT_MAX) continue;
                    if (A[i]+dp[j] < dp[i]) {
                        dp[i] = A[i]+dp[j];
                        pos[i] = j;
                    }
                }
            }
            // cannot jump to An
            if (dp[0] == INT_MAX) return ans;
            int k = 0;
            while (k != -1) {
                ans.push_back(k+1);
                k = pos[k];
            }
            return ans;
        }
    };
    

  • 0
    G

    forward approach also works!!


  • 0
    T

    Your solution is great!
    Here is a Java Version:

    public class Solution {
        public List<Integer> cheapestJump(int[] A, int B) {
            List<Integer> res = new ArrayList<>();
            if(A==null || A.length<1 || A[A.length-1]<0){
                return res;
            }
            int[] forward = new int[A.length];
            int[] cost = new int[A.length];
            Arrays.fill(forward,-1);
            Arrays.fill(cost,Integer.MAX_VALUE);
            cost[A.length-1]=A[A.length-1];
            for(int i=forward.length-2;i>=0;i--){
                 if(A[i]==-1){
                     continue;
                 } 
                 for(int j=i+1;j<=Math.min(i+B,A.length-1);j++){
                     if(cost[i]>cost[j]+A[i]&&cost[j]!=Integer.MAX_VALUE){
                         cost[i]=cost[j]+A[i];
                         forward[i]=j;
                     }
                 } 
            }
            
            if(cost[0]==Integer.MAX_VALUE){
                return res;
            }
            int k=0;
            while(k!=-1){
                res.add(k+1);
                k=forward[k];
            }
            return res;
        }
    }
    
    

  • 2
    L

    I'm just wondering why we must walk backwards? It seems that walking forward will not get the solution.


  • 0
    J

    "If considering smaller index first, i+1 to i+B, there is no need to worry about lexicographical order."

    Could explain why this is the case? Is it just so you make the smallest jump and get the longest path with the same cost?


  • 0
    Z

    @jamarshon I have added more detailed explanation in the post. Hopeful it explains.


  • 0
    E

    @leet2016 We walk backwards because of the subproblem dependency.

    To find the min cost path from position 0->n with steps up to B, we would need to find find the min between the follow options: min path cost of 1->N, 2->N, ...B->N and then add the cost of A[0]. How do we find the min path cost of 1->N? well, we would need to calculate min path cost of 2->N, 3->N, ...B+1->N.

    There are a lot of subproblems that repeat. Going backwards allows us to use a clean iterative approach, because by the time you are finding the answer for i->n, we have answers for i+1->n, i+2->n, ... n-1->n already.


  • 1
    D

    @leet2016 It is OK to walk forward. But it is difficult to find the lexicographically smallest path when there are two or more paths having the same minimum cost. I've tried a stupid method which got accepted. My method is to record the optimal path for each subproblem, i.e. optimal path from A1 to Ai, and compare all candidate paths lexicographically. Obviously, it took more time and space.


  • 0
    S
    This post is deleted!

  • 0
    P
    This post is deleted!

  • 4
    X

    Great solution!
    I think using the backward approach in the dynamic programming solution is determined by the nature of the lexicographical order. In a path, elements in a lower position are more important.

    1. Problems with the forward approach:
      As it goes from 1 to n, we lose the prefix of the current optimal path for each possible previous jump. To avoid losing this information, we need to explicitly track all of the whole optimal paths for each previous index, which is not sufficient.

    2. With the backward approach, we always focus on the left-most elements on a path. At index i, if we have two optimal paths path_1 and path_2 with the same cost, they have different next jumps jmp_i and jmp_j, we alway select the path with a lower index min(jmp_i, jmp_j) for the next jump.


  • 0

    In case we're allowed to change the input array !

    class Solution {
    public:
        vector<int> cheapestJump(vector<int>& A, int B) {
            int N = A.size();
            if (A[N-1]==-1 || A[0]==-1) return {};
            
            vector<int> next(N, -1);
            next[N-1] = N;
            
            for (int i=N-1;i>=1;i--){
                
                if (A[i-1]==-1) continue;
                
                int mini=INT_MAX;
                for (int j=i+1;j<=min(N, i+B);j++){
                    if (A[j-1]==-1) continue;
                    
                    if (A[j-1]<mini){
                        mini = A[j-1];
                        next[i-1] = j-1;
                    }
                }
                if (mini != INT_MAX){
                    A[i-1] += mini;
                }else
                    A[i-1] = -1;
            }
            
            vector<int> res;
            res.push_back(1);
            int idx = next[0];
            while (idx != N){
                if (idx==-1) return {};
                res.push_back(idx+1);
                idx = next[idx];
            }
            return res;
        }
    };
    

  • 1

    @eidehua @Diaoge thank you for explaining the difference between using walk forward and walk backwards! Me too stuck using dp walk forwards , and have to do similar walkaround solution to @Diaoge -- record every optimal path for each subproblem.


  • 0
    B

    @coder42 For completeness here's my walking forward solution, O(B*n^2) time worst case (though much better average case and still beating 9%) and O(n^2) space (definitely not optimal!), basically storing the pair<smallest cost to that point, smallest lexicographically path to that point>, I used C++'s built comparison for pair and vector (element by element & lexicongraphical).

    vector<int> cheapestJump(vector<int>& A, int B) {
            int n=A.size();
            vector<pair<long,vector<int>>> paths(n,{INT_MAX,{INT_MAX}});
            paths[0]={0,{1}};
            for (int i=0; i<n; i++) {
                long coins=paths[i].first;
                vector<int> path = paths[i].second;
                for (int j=i+1; j<=i+B && j<n; j++) {
                    if (A[j]==-1) continue;
                    
                    coins+=A[j];
                    path.push_back(j+1);
                    if (make_pair(coins,path} < paths[j]) paths[j]={coins,path};
                    coins-=A[j];
                    path.pop_back();
                }
            }
            
            return paths[n-1].first==INT_MAX ? vector<int>() : paths[n-1].second;
        }
    

Log in to reply
 

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