LeetCode 656. 金币路径（DP）

样例 1 :
输入: [1,2,4,-1,2], 2
输出: [1,3,5]
 
样例 2 :
输入: [1,2,4,-1,2], 1
输出: []
 
注释 :
路径 Pa1，Pa2，……，Pan 是字典序小于 Pb1，Pb2，……，Pbm 的，
	当且仅当第一个 Pai 和 Pbi 不同的 i 满足 Pai < Pbi，
	如果不存在这样的 i 那么满足 n < m。
A1 >= 0。 
A2, ..., AN （如果存在） 的范围是 [-1, 100]。
A 数组的长度范围 [1, 1000].
B 的范围 [1, 100].

class Solution {
public:
    vector<int> cheapestJump(vector<int>& A, int B) {
        int n = A.size(), i, len, cost, idx = n-1;
        vector<int> dp(n, INT_MAX);
        vector<vector<int>> path(n);
        dp[0] = A[0];
        path[0] = {1};
        for(i = 0; i < n-1; i++) 
        {
        	if(dp[i] == INT_MAX)//状态不存在
        		continue;
        	for(len = 1; len <= B; len++)
        	{
        		if(i+len < n && A[i+len] != -1)//可以到达
        		{
        			if(dp[i+len] > dp[i]+A[i+len])
        			{	//取最小的花费的路径
        				dp[i+len] = dp[i]+A[i+len];
        				path[i+len] = path[i];
        				path[i+len].push_back(i+len+1);
        			}
        			else if(dp[i+len] == dp[i]+A[i+len])
        			{	//花费相同
        				auto temp = path[i];
        				temp.push_back(i+len+1);
        				if(temp < path[i+len])//取字典序小的路径
        					path[i+len] = temp;
        			}
        		}
        	}
        }
        return path[n-1];
    }
};