LWC 61:741. Cherry Pickup

LWC 61:741. Cherry Pickup

传送门:741. Cherry Pickup

Problem:

In a N x N grid representing a field of cherries, each cell is one of three possible integers. 0 means the cell is empty, so you can pass through; 1 means the cell contains a cherry, that you can pick up and pass through; -1 means the cell contains a thorn that blocks your way. Your task is to collect maximum number of cherries possible by following the rules below: Starting at the position (0, 0) and reaching (N-1, N-1) by moving right or down through valid path cells (cells with value 0 or 1); After reaching (N-1, N-1), returning to (0, 0) by moving left or up through valid path cells; When passing through a path cell containing a cherry, you pick it up and the cell becomes an empty cell (0); If there is no valid path between (0, 0) and (N-1, N-1), then no cherries can be collected.

Example 1:

Input: grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]] Output: 5 Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2). 4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]]. Then, the player went left, up, up, left to return home, picking up one more cherry. The total number of cherries picked up is 5, and this is the maximum possible.

Note:

Grid is an N by N 2D array, with 1 <= N <= 50.

Each grid[i][j] is an integer in the set {-1, 0, 1}.

It is guaranteed that grid[0][0] and grid[N-1][N-1] are not -1.

思路: 先出再回来。实际上可以看作两条出发的线抵达N-1即可。此处的trick在于被选择后的状态该如何记录。实际上如果去的时候两条路线重合的话只会加一次cherry。此题采用递归+记忆化的手段,当然因为借鉴了别人的思路,所以具体的解题演变过程在此处就无法展示了。在代码中列举一些自己的comment吧。

Java版本:

    public int cherryPickup(int[][] grid) {
        n = grid.length;
        m = grid[0].length;

        v = new int[n][m];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                v[i][j] = grid[i][j];
            }
        }

        mem = new int[52][52][52];
        for (int i = 0; i < 52; ++i) {
            for (int j = 0; j < 52; ++j) {
                for (int k = 0; k < 52; ++k) {
                    mem[i][j][k] = -1;
                }
            }
        }

        // grid[0][0] 始终会被访问到,f在求解问题时,是从起点出发(不包含起点)的最大cherry数
        int ans = f(0, 0, 0, 0) + grid[0][0];
        return ans < -10000 ? 0 : ans;
    }

    int[][] v;
    int n, m;
    int INF = 0x3f3f3f3f;

    int[][][] mem;

    int[] dx = {1, 0};
    int[] dy = {0, 1};
    int f(int x1, int y1, int x2, int y2) {
        // 一旦抵达终态则范围0, 因为此处f的最大cherry数不包含起点,所以终态才为 (n - 1, m - 1)
        if (x1 == n - 1 && y1 == m - 1) return 0;
        // x2一旦确定,y2跟着确定,没必要记录y2的状态
        if (mem[x1][y1][x2] != -1) return mem[x1][y1][x2];
        int ans = -INF;

        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                // 只能往右 和 往下
                int nx1 = x1 + dx[i];
                int ny1 = y1 + dy[i];

                int nx2 = x2 + dx[j];
                int ny2 = y2 + dy[j];

                if (nx1 >= 0 && nx1 < n && nx2 >= 0 && nx2 < n && ny1 >= 0 && ny1 < m && ny2 >= 0 && ny2 < m) {
                    if (v[nx1][ny1] == -1) continue;
                    if (v[nx2][ny2] == -1) continue;

                    if (nx1 == nx2 && ny1 == ny2) {
                        // 重合的情况,只需加一次cherry,第一次取cherry,第二次经过但无cherry可取
                        ans = Math.max(ans, v[nx1][ny1] + f(nx1, ny1, nx2, ny2));
                    }
                    else {
                        // 去取一次cherry,回也取一次cherry
                        ans = Math.max(ans, v[nx1][ny1] + v[nx2][ny2] + f(nx1, ny1, nx2, ny2));
                    }
                }
            }
        }
        return mem[x1][y1][x2] = ans;
    }

Python 版本:(超时)

    def cherryPickup(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        m = len(grid[0])

        dp = dict()
        dx = [1, 0]
        dy = [0, 1]

        INF = 0x3f3f3f3f;

        def f(x1, y1, x2, y2):
            if (x1 == n - 1 and y1 == m - 1): return 0
            if ((x1, y1, x2) in dp): return dp[(x1, y1, x2)]

            ans = -INF
            for i in range(2):
                for j in range(2):
                    nx1 = x1 + dx[i]
                    ny1 = y1 + dy[i]

                    nx2 = x2 + dx[j]
                    ny2 = y2 + dy[j]

                    if (nx1 >= 0 and nx1 < n and ny1 >= 0 and ny1 < m and nx2 >= 0 and nx2 < n and ny2 >= 0 and ny2 < m):
                        if (grid[nx1][ny1] == -1): continue
                        if (grid[nx2][ny2] == -1): continue

                        if (nx1 == nx2 and ny1 == ny2):
                            ans = max(ans, grid[nx1][ny1] + f(nx1, ny1, nx2, ny2))
                        else:
                            ans = max(ans, grid[nx1][ny1] + grid[nx2][ny2] + f(nx1, ny1, nx2, ny2))

            dp[(x1, y1, x2)] = ans
            return ans

        ans = f(0, 0, 0, 0) + grid[0][0]
        if ans < -10000: return 0
        return ans        

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Web 开发

毕业照的时候没入相机,去旅游了必须入手

之前在学生会,用了一年的500D,对单反没啥感觉。反倒是微单,携带方便,可玩性和实用性都很高。某水鱼之前的GF1,某阳杰的GF2,再到一个大明星的GX1,看到G...

770
来自专栏VRPinea

VR动画电影《Raising a Rukus》|一对熊孩子的异世界探险之旅

VR动画电影《Raising a Rukus(拉克斯的魔幻旅程)》,讲述的是一对双胞胎在生日那天,与他们新获得的狗狗一起探险异世界的故事。

1211
来自专栏CSDN技术头条

我被程序员打了!!

本来这事,以我腼腆的性格我是不想说的,昨晚上被俩程序员打!了!哥们内心实在是憋屈!在这里一吐为快!

1042
来自专栏SeanCheney的专栏

如何模仿教父

FBI网站有组织犯罪的页面专门有介绍Cosa nostra:https://www.fbi.gov/investigate/organized-crime/hi...

1231
来自专栏deed博客

【搜狐】神吐槽:运营商威武 短信收复仁爱礁

1573
来自专栏小狼的世界

惊闻NBC在奥运后放弃使用Silverlight

奥运初始的时候,媒体对于NBC使用Silverlight技术进行了高调的宣传,没想到奥运会结束刚刚三周的时间,NBC就弃用了Siverlight,重新采用Ado...

1042
来自专栏VRPinea

智能家居应用|三星套路玩的深,AR走进格里芬

901
来自专栏TEG云端专业号的专栏

【腾讯AI LAB出品】日漫风的腾讯大楼,静守时光,以待流年

渐渐地,残星闭上昏昏欲睡的眼睛,在晨空中隐隐作退,夜空似藏青色的帷幕,点缀着闪闪繁星,让人不由深深地沉醉。AI Lab 出品的视频滤镜和新海诚滤镜,便是聚光灯下...

3535
来自专栏IT派

警方通报空姐遇害!滴滴100万悬赏嫌疑司机!请转发找凶手!

5月10日晚23:17,平安郑州发布关于空姐李明珠搭乘滴滴顺风车遇害案的警情通报!

1363
来自专栏区块链大本营

冻结黑客账户!6万EOS被盗的最新仲裁结果出来了

近期大热的EOS版狼人杀遭遇黑客攻击,60686.4190个EOS被盗,上线不到2天的EOS狼人游戏被迫停服。

532

扫码关注云+社区