leetcode：656. 金币路径（会员题）

题目

给定一个数组 A（下标从 1 开始）包含 N 个整数：A1，A2，……，AN 和一个整数 B。
你可以从数组 A 中的任何一个位置（下标为 i）跳到下标 i+1，i+2，……，i+B 的任意一个可以跳到的位置上。
如果你在下标为 i 的位置上，你需要支付 Ai 个金币。
如果 Ai 是 -1，意味着下标为 i 的位置是不可以跳到的。

现在，你希望花费最少的金币从数组 A 的 1 位置跳到 N 位置，你需要输出花费最少的路径，依次输出所有经过的下标（从 1 到 N）。
如果有多种花费最少的方案，输出字典顺序最小的路径。
如果无法到达 N 位置，请返回一个空数组。

示例：

  1. 输入: [1,2,4,-1,2], 2
  2. 输出: [1,3,5]
输入: [1,2,4,-1,2], 1
输出: []

解答 & 代码

动态规划：

额外使用 **vector<vector<int>> paths**记录最少花费的路径，path[i] 代表从下标 1 走到下标 i+1 的最少花费路径

  • 动态规划数组 **dp**：dp[i] 代表从下标 1 走到下标 i+1 的最少花费
  • 状态转移方程：dp[i] = min(dp[i-step] + A[i])
    • 要求下标 i+1 本身是可达的，i-step>=0，下标 i-step+1 可达
    • 同时更新最小花费路径，如果存在多种花费最少的方案，要取字典序最小的路径，可以直接比较 vector 形式的 path，**vector** 数组直接比较就是按字典序比较
  • 初始化：所有 dp[i] 初始化为 INT_MAX
    • dp[0] = A[0]，paths[0] = {1} ```cpp

      include

      include

      using namespace std;

vector cheapestJump(vector& A, int B) { int len = A.size(); // 动态规划数组 dp：dp[i] 代表从下标 1 走到下标 i+1 的最少花费 vector dp(len, INT_MAX); // 全部初始化为 INT_MAX // 最少花费路径：path[i] 代表从下标 1 走到下标 i+1 的最少花费路径 vector> paths(len);

// 初始化
dp[0] = A[0];        // 走到下标 1 的花费    
paths[0] = {1};        // 走到下标 1 的最少花费的路径

// 状态转移
for(int i = 1; i < len; ++i)
{
    // 如果下标 i + 1 不可达，则跳过
    if(A[i] == -1)
        continue;
    // 遍历走到位置 i + 1 最后一步所有可能的步长 [1, B]
    for(int step = 1; step <= B && i - step >= 0; ++step)
    {
        // 如果上一步 i - step 是可达的
        if(A[i - step] != -1 && dp[i - step] != INT_MAX)
        {
            // 如果从 i- step 跳到 i 的花费最少，则更新状态
            if(dp[i - step] + A[i] < dp[i])
            {
                dp[i] = dp[i - step] + A[i];
                paths[i] = paths[i - step];
                paths[i].push_back(i + 1);
            }
            // 如果从 i- step 跳到 i 是花费最少的方案之一，则选择字典序最小的路径
            else if(dp[i - step] + A[i] == dp[i])
            {
                vector<int> tempPath = paths[i - step];
                tempPath.push_back(i + 1);
                // 注意：vector 数组直接比较大小就是比较字典序！！！
                if(tempPath < paths[i])
                    paths[i] = tempPath;
            }
        }
    }
}

// 返回走到下标 len 的最小花费路径
return paths[len - 1];

}

int main() { vector A = {1, 2, 4, -1, 2}; int B = 2; vector cheapestPath = cheapestJump(A, B); for(int i = 0; i < cheapestPath.size(); ++i) cout << cheapestPath[i] << “ “; cout << endl;

return 0;

}

`` 复杂度分析：设数组A` 长为 N，最大步长为 B

  • 时间复杂度 O(NB)：
  • 空间复杂度[困难] 656. 金币路径 - 图1：