1575. 统计所有可行路径 - Kotlin 基于BFS的动态规划

Problem: 1575. 统计所有可行路径

思路

基于BFS的思路，设dp[a][b]为从start出发，燃油为fuel，达到城市a时剩余燃油b的可能路径

自然地，我们应当从dp[start][fuel]开始考虑，遍历locations中的所有城市city，达到该城市需要消耗的燃油即abs(locations[city] - locations[start])，当该值<city时说明可以前往该城市，则该城市的路径数应当+=dp[start][fuel]，对于初始情况，dp[start][fuel]=1

此时该状态下剩余的燃油为fuel-abs(locations[city] - locations[start])，我们已知dp[city][fuel-abs(locations[city] - locations[start])]是一个可到达的情况，则将该状态加入BFS队列中

同样，一般地，对于一个可以到达的情况dp[cityNow][fuelNow]，遍历locations中的所有城市target，若abs(locations[target] - locations[cityNow]) <= fuelNow则说明该城市是可以从当前状态到达的，则dp[city][fuel-abs(locations[target] - locations[cityNow])] += dp[cityNow][fuelNow]。同时，若该可到达的状态没有加入BFS队列中，则将其加入以待后续遍历

BFS的重点在于应当从燃油剩余量的从多到少顺序遍历，当我们考虑燃油较多的情况时，只会去更新燃油较少的情况，而不会干涉到之前的情况，保证了DP算法的无后效性，这里我用了一个优先队列来实现

由于我们并不在意达到final时的剩余燃油量，因此直接输出dp[final].sum()
即可，取余操作自行添加即可

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution {
    fun countRoutes(locations: IntArray, start: Int, finish: Int, fuel: Int): Int {
        //每个状态以一个数对表示，pair[0]表示当前城市，pair[1]表示剩余燃油量
        //有效队列按照状态的剩余燃油的降序排列
        val bfs = PriorityQueue<IntArray> { a, b -> b[1] - a[1] }
        val dp = Array(locations.size) { LongArray(fuel + 1) { 0 } }
        val skip = Array(locations.size) { BooleanArray(fuel + 1) { false } }
        bfs.add(intArrayOf(start, fuel))
        dp[start][fuel] = 1

        while (bfs.isNotEmpty()) {
            val status = bfs.remove()
            for ((index, position) in locations.withIndex()) {
                //不考虑原地不动的情况
                if (index == status[0]) {
                    continue
                }
                //消耗燃油大于剩余燃油，该状态无法到达
                if (Math.abs(position - locations[status[0]]) > status[1]) {
                    continue
                }
                dp[index][status[1] - Math.abs(position - locations[status[0]])] += dp[status[0]][status[1]]
                dp[index][status[1] - Math.abs(position - locations[status[0]])] %= (1e9+7).toLong()
                //将可到达的情况加入队列中
                if (!skip[index][status[1] - Math.abs(position - locations[status[0]])]) {
                    skip[index][status[1] - Math.abs(position - locations[status[0]])] = true
                    bfs.add(intArrayOf(index, status[1] - Math.abs(position - locations[status[0]])))
                }
            }
        }

        return (dp[finish].sum() % ((1e9+7).toLong())).toInt()
    }
}