传送门 LeeCode 1575. 统计所有可行路径
d p [ i ] [ j ] dp[i][j] dp[i][j] 代表从 s t a r t start start 出发，到达城市 i i i 且剩余汽油总量为 j j j 的方案数，则有递推 d p [ i ] [ j ] = ∑ i ! = i ′ 且 a b s ( l o c a t i o n [ i ] − l o c a t i o n [ i ′ ] ) + j ≤ f u e l d p [ i ′ ] [ j + a b s ( l o c a t i o n [ i ] − l o c a t i o n [ i ′ ] ) ] dp[i][j]=\sum\limits_{i!=i'且abs(location[i]-location[i'])+j\leq fuel} dp[i'][j+abs(location[i]-location[i'])] dp[i][j]=i!=i′且abs(location[i]−location[i′])+j≤fuel∑dp[i′][j+abs(location[i]−location[i′])]
class Solution { #define maxl 105 #define maxf 205 public: int s, fuel, mod = 1000000007; int dp[maxl][maxf]; int rec(int t, int f, vector<int> &loc) { if (dp[t][f] != -1) return dp[t][f]; if (f == fuel) return t == s ? 1 : 0; int res = 0; for (int i = 0; i < loc.size(); i++) { int d; if (i != t && (d = abs(loc[i] - loc[t])) <= (fuel - f)) res += rec(i, f + d, loc); if (res >= mod) res -= mod; } return dp[t][f] = res; } int countRoutes(vector<int> &locations, int start, int finish, int fuel) { memset(dp, -1, sizeof(dp)); this->s = start, this->fuel = fuel; int res = 0; for (int i = 0; i <= fuel; i++) { res += rec(finish, i, locations); if (res >= mod) res -= mod; } return res; } };