动态规划算法加速：阿里巴巴捡硬币问题O(n²)解法优化咨询

一条道路上散落着一些金币，每个金币的位置由一个整数表示——距离起点0米的距离。所有金币都位于起点右侧，且与起点的距离各不相同。阿里巴巴从时间0开始沿路奔跑收集金币，他每秒恰好跑1米。每个金币都有一个截止时间，必须在此之前被捡起，否则会消失。阿里巴巴必须收集所有金币，并尽可能缩短耗时。他可以从线上任意点出发，按任意顺序收集金币，但必须收集全部金币并最小化总耗时。

示例 #

输入：
第一行包含整数n（n ≤ 10000）——金币数量。接下来n行每行包含两个整数d和t，前者表示金币的位置（1 ≤ d ≤ 10000），后者表示必须捡起金币的截止时间（1 ≤ t ≤ 10000，恰好在时间t时也可捡起金币）。金币按距离起点由近到远（从左到右）的顺序给出。

input.txt：

5
1 3
3 1
5 8
8 19
10 15

output.txt：

11

针对该问题可得出的结论：
对于任意金币子序列，收集完成时要么在第一个金币处，要么在最后一个金币处。

dp[i][j]
设数组dp[i][j]为覆盖金币区间(i...j)所需的最短时间，假设最终停留在金币j处。

最优子结构：
考虑区间i..j，收集完成时可停在金币i或j处。若最终停在j处，则可通过解决子问题[i..j-1]后从j-1移动到j，或解决子问题[j..i+1]（i+1 < j）后从i+1移动到j。同理，若最终停在i处，可从之前子问题的两个端点扩展到更大问题。

基准情况：
若i = j，则dp[i][j] = 0，因为可以从任意金币出发。

带记忆化的DP实现

std::vector<coin> in; // input array
std::vector<std::vector<int64_t>> dp; // with default values = -1;

int64_t dist(const coin& cstart, const coin& cend, int64_t prev_time) {
    if(cend.ctime - prev_time - std::abs(cend.cdist - cstart.cdist) >= 0)
        return std::abs(cend.cdist - cstart.cdist);
    else 
        return INT64_MAX;
}

int64_t F(size_t i, size_t j) {
    if (i == j) {
        dp[i][j] = 0;
    } else if(dp[i][j] == -1) {
        if(j > i){
            int64_t i_to_j_min_1 = F(in, dp, i, j - 1);
            int64_t j_min_1_to_i = F(in, dp, j - 1, i);
            dp[i][j] = std::min(add(i_to_j_min_1, dist(in[j - 1], in[j], i_to_j_min_1)) , 
                                add(j_min_1_to_i, dist(in[i], in[j], j_min_1_to_i)));

            int64_t i_plus_1_to_j = F(in, dp, i + 1, j);
            int64_t j_to_i_plus_1 = F(in, dp, j, i + 1);
            dp[j][i] = std::min(add(i_plus_1_to_j, dist(in[j], in[i], i_plus_1_to_j)),
                                add(j_to_i_plus_1, dist(in[i + 1], in[i], j_to_i_plus_1)));
        }
    }
    return dp[i][j];
}

能否对该算法进行加速优化？

内容的提问来源于stack exchange，提问作者NJrslv