c++ - 动态规划 : Calculate all possible end positions for a list of consecutive jumps

Question

问题在于计算所有可能的结束位置以及每个位置存在多少种组合。

给定起始位置 x=0、轨道长度 m 和跳跃列表。返回区间 [-m/2,+m/2] 上每个位置的可能端数。跳跃必须按照给定的相同顺序完成，但可以以消极或积极的方式完成。

例如:

L = 40
jumps = 10, 10

解决方法:

-20 : 1  (-10, -10)
0 : 2 (-10,+10 & +10,-10)
20 : 1 (+10,+10)

(需要的输出只是一对“位置:#combinations”)

我用简单的递归做了，结果还可以。但是在大数据集中，执行时间是几分钟或几小时。我知道通过动态规划我可以在几秒钟内找到解决方案，但我不知道在这种情况下如何应用动态规划。

这是我实际的递归函数:

void escriuPosibilitats(queue<int> q, map<int,int> &res, int posicio, int m) {
    int salt = q.front();
    q.pop();
    if(esSaltValid(m,posicio,-salt)) {
        int novaPosicio = posicio - salt;
        if(q.empty()) {
            res[novaPosicio]++;
        } else {
            escriuPosibilitats(q,res,novaPosicio,m);
        }
    }
    if(esSaltValid(m,posicio,salt)) {
        int novaPosicio = posicio + salt;
        if(q.empty()) {
            res[novaPosicio]++;
        } else {
            escriuPosibilitats(q,res,novaPosicio,m);
        }
    }
}

1. 其中q是剩余跳转的队列。
2. res 是局部解。
3. posicio 是实际位置。
4. m 是轨道的长度。
5. 其中 esSaltValid 是一个函数，用于检查跳跃在轨道长度范围内是否有效。

PD:对不起我的英语水平。我试图改善我的问题!谢谢 =)

Answer 1

您可以使用以下想法。设 dp[x][i] 是在第 i 次跳跃之前使用的到达位置 x 的方法数。那么每个 x 的答案就是 dp[x][N]，其中 N 是跳跃的次数。更重要的是，你可以意识到这个 dp 只依赖于前一行，然后你可以简单地 dp[x] 并将下一行保存在一些辅助数组中，然后在每次迭代中替换它。代码将是这样的:

const int MOD = (int)(1e8+7);
    const int L = 100;
    int N = 36;
    int dx[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

    int dp[L+1];
    int next[L+1];

    int main() {
      int shift = L/2; // to handle negative indexes
      dp[shift] = 1; // the initial position has one way to arrive, since you start there
      for (int i = 0; i < N; ++i) { // for each jump size
        for (int x = -L/2; x <= L/2; ++x) { // for each possible position
          if (-L/2 <= x + dx[i] && x + dx[i] <= L/2) // positive jump
            next[x + shift] = (next[x + shift] + dp[x + dx[i] + shift]) % MOD;
          if (-L/2 <= x - dx[i] && x - dx[i] <= L/2) // negative jump
            next[x + shift] = (next[x + shift] + dp[x - dx[i] + shift]) % MOD;
        }
        for (int x = -L/2; x <= L/2; ++x) { // update current dp to next and clear next
          dp[x+shift] = next[x+shift];
          next[x+shift] = 0;
        }
      }
      for (int x = -L/2; x <= L/2; ++x) // print the result
        if (dp[x+shift] != 0) {
          cout << x << ": " << dp[x+shift] << '\n';  
        }
    }

当然，如果 L 太大无法处理，您可以压缩状态空间并将结果保存在映射中，而不是数组中。该方法的复杂度为 O(L*N)。希望对您有所帮助。

编辑:只需计算所有模数 1e8+7 即可。