LeetCode之Unique Paths II（Kotlin）

问题：

方法：
首先第一个思路是DFS，但是不符合题目的时间复杂度要求。然后因为题目限定只能向右或者向下移动，所以可以使用动态规划，推导出DP(i)(j) = DP(i-1)(j) + DP(i)(j-1)，i，j为格子的坐标，即到当前位置可能的路径必是从左边格子或者上边格子而来，可以参考下方代码实现。

具体实现：

class UniquePathsII {
    fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        val dp = Array(obstacleGrid.size) { IntArray(obstacleGrid[0].size) { 0 } }
        if (obstacleGrid[0][0] == 1) {
            dp[0][0] = 0
        } else {
            dp[0][0] = 1
        }
        for (i in obstacleGrid.indices) {
            for (j in obstacleGrid[0].indices) {
                if (i == 0 && j == 0) {
                    continue
                } else if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0
                } else if (i - 1 < 0) {
                    dp[i][j] = dp[i][j - 1]
                } else if (j - 1 < 0) {
                    dp[i][j] = dp[i - 1][j]
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                }
            }
        }
        return dp[dp.lastIndex][dp[0].lastIndex]
    }
}

fun main(args: Array<String>) {
    val input = arrayOf(intArrayOf(0, 0, 0), intArrayOf(0, 1, 0), intArrayOf(0, 0, 0))
    val uniquePathsII = UniquePathsII()
    println(uniquePathsII.uniquePathsWithObstacles(input))
}

有问题随时沟通

具体代码实现可以参考Github