deno.land / x / masx200_leetcode_test@10.6.5 / count-all-possible-routes / index.ts
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465export default function countRoutes( locations: number[], start: number, finish: number, fuel: number,): number { const MOD = 1000000007;
const n = locations.length; const startPos = locations[start]; const finishPos = locations[finish];
locations.sort((a, b) => a - b); for (let i = 0; i < n; ++i) { if (startPos == locations[i]) { start = i; } if (finishPos == locations[i]) { finish = i; } }
const dpL = Array(n) .fill(0) .map(() => Array<number>(fuel + 1).fill(0)); const dpR = Array(n) .fill(0) .map(() => Array<number>(fuel + 1).fill(0));
dpL[start][0] = dpR[start][0] = 1;
for (let used = 0; used <= fuel; ++used) { for (let city = n - 2; city >= 0; --city) { const delta = locations[city + 1] - locations[city]; if (used >= delta) { dpL[city][used] = ((((used == delta ? 0 : dpL[city + 1][used - delta]) * 2) % MOD) + dpR[city + 1][used - delta]) % MOD; } } for (let city = 1; city < n; ++city) { const delta = locations[city] - locations[city - 1]; if (used >= delta) { dpR[city][used] = ((((used == delta ? 0 : dpR[city - 1][used - delta]) * 2) % MOD) + dpL[city - 1][used - delta]) % MOD; } } }
let ans = 0; for (let used = 0; used <= fuel; ++used) { ans += (dpL[finish][used] + dpR[finish][used]) % MOD; ans %= MOD; } if (start == finish) { ans = (ans + MOD - 1) % MOD; } return ans;}
Version Info