1463. 摘樱桃 II - Kotlin 多维DP

Problem: 1463. 摘樱桃 II

思路

定义在grid[0][0]处的机器人为a，在grid[0][grid[0].size-1]处的机器人为b

由题意我们可以知道，在任意一步中，机器人a与机器人b都是在同一行的

dp[row][a][b]定义为两个机器人分别在第row行的对应列时，摘到樱桃的最大数量，我们可以初始化为Int.MIN_VALUE，定义该值为无法到达的情况

• 理所当然的，对于dp[0]，应当dp[0][0][grid[0].size-1]初始化为grid[0][0]+grid[0][grid[0].size-1]，其他值均初始化为Int.MIN_VALUE

由于a和b都各自有三种移动方向（左下、正下和右下），因此两个机器人一共有九种移动的组合方式，最好通过一个direction数组记录下预设的组合方式，减少后续代码的复杂度

我们按照行号（0 until grid.size）进行遍历，并让a、b遍历所有可能性，即

for (row in 0 until grid.size - 1) {
    for (a in 0 until grid[row].size) {
        for (b in 0 until grid[row].size) {
            ...
        }
    }
}   

对于我们得到的dp[row][a][b]，值为Int.MIN_VALUE的情况不可到达，应当直接continue，对于可行的情况，遍历九种移动方式，即

• aNext=a+direction[0]
• bNext=b+direction[b]

我们可以从dp[row][a][b]这个位置状态，令两个机器人移动一次前进到dp[row+1][aNext][bNext]这个状态

• 此时有dp[row+1][aNext][bNext]=max(dp[row+1][aNext][bNext],dp[row][a][b] + grid[row + 1][aNext] + grid[row + 1][bNext]
• 要考虑到特殊情况：当aNext==bNext时，机器人仅有一个能摘取樱桃，应当计算dp[row][a][b] + grid[row + 1][aNext]，即少计算一次grid

对于dp[grid.size-1]中的所有情况求最大值即可

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution {
    fun cherryPickup(grid: Array<IntArray>): Int {
        val dp = Array(grid.size) { Array(grid[0].size) { IntArray(grid[0].size) { Int.MIN_VALUE } } }
        val direction = arrayOf(
            intArrayOf(0, 0),
            intArrayOf(1, 0),
            intArrayOf(0, 1),
            intArrayOf(1, 1),
            intArrayOf(-1, 0),
            intArrayOf(0, -1),
            intArrayOf(-1, -1),
            intArrayOf(1, -1),
            intArrayOf(-1, 1)
        )
        var max = Int.MIN_VALUE
        dp[0][0][grid[0].size - 1] = grid[0][0] + grid[0][grid[0].size - 1]

        for (row in 0 until grid.size - 1) {
            for (a in 0 until grid[row].size) {
                for (b in 0 until grid[row].size) {
                    if (dp[row][a][b] == Int.MIN_VALUE) {
                        continue
                    }

                    for (dir in direction) {
                        val aNext = a + dir[0]
                        val bNext = b + dir[1]

                        if (aNext < 0 || aNext >= grid[row].size || bNext < 0 || bNext >= grid[row].size) {
                            continue
                        }

                        if (aNext != bNext) {
                            dp[row + 1][aNext][bNext] = Math.max(
                                dp[row + 1][aNext][bNext],
                                dp[row][a][b] + grid[row + 1][aNext] + grid[row + 1][bNext]
                            )
                        } else {
                            dp[row + 1][aNext][bNext] =
                                Math.max(dp[row + 1][aNext][bNext], dp[row][a][b] + grid[row + 1][aNext])
                        }

                        if (row == grid.size - 2) {
                            max = Math.max(max, dp[row + 1][aNext][bNext])
                        }
                    }
                }
            }
        }
        return max
    }
}