LeetCode 1463: Cherry Pickup II

Question

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0), and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots by following the rules below:

• From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
• When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
• When both robots stay on the same cell, only one of them takes the cherries.
• Both robots cannot move outside of the grid at any moment.
• Both robots should reach the bottom row in the grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24

Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, \$(3 + 2 + 5 + 2) = > 12\$.
Cherries taken by Robot #2, \$(1 + 5 + 5 + 1) = 12\$.
Total of cherries: \$12 + 12 = 24\$.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]

Output: 28

Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, \$(1 + 9 + 5 + 2) = 17\$.

Cherries taken by Robot #2, \$(1 + 3 + 4 > + 3) = 11\$.

Total of cherries: \$17 + 11 = 28\$.

Constraints:

• \$rows == grid.length\$
• \$cols == grid[i].length\$
• \$2 <= rows, cols <= 70\$
• \$0 <= grid[i][j] <= 100 \$

Inputs

[[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
[[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
[[1,10,0,3,86,40],[0,0,0,3,86,40],[0,0,3,3,86,40],[9,0,3,3,86,40], [1,0,40,3,86,40],[0,22,0,3,86,40],[99,0,3,3,86,40],[9,0,3,3,86,40]]

Outputs

24
22
819

Code

#include <vector>
#include <cstring>

struct Solution {
    int map_cherries[70][70][70] = {};

    inline int cherryPickup(std::vector<std::vector<int>> &grid) {
        std::memset(map_cherries, -1, sizeof(map_cherries));
        const int row_length = grid.size();
        const int col_length = grid[0].size();
        return depth_first_search(grid, row_length, col_length, 0, 0, col_length - 1);
    }

private:
    const inline int depth_first_search(
        std::vector<std::vector<int>> &grid,
        const int row_length,
        const int col_length,
        int row,
        int left_robot,
        int right_robot
    ) {
        if (row == row_length) {
            return 0;
        }

        if (map_cherries[row][left_robot][right_robot] != -1) {
            return map_cherries[row][left_robot][right_robot];
        }

        int max_cherries = 0;

        for (int left = -1; left < 2; left++) {
            for (int right = -1; right < 2; right++) {
                const int curr_left_robot = left_robot + left;
                const int curr_right_robot = right_robot + right;

                if (curr_left_robot > -1 and curr_left_robot < col_length and curr_right_robot > -1 and curr_right_robot < col_length) {
                    max_cherries = std::max(max_cherries, depth_first_search(
                                                grid,
                                                row_length,
                                                col_length,
                                                row + 1,
                                                curr_left_robot,
                                                curr_right_robot
                                            ));
                }
            }
        }

        int cherries = grid[row][left_robot];

        if (left_robot != right_robot) {
            cherries += grid[row][right_robot];
        }

        return map_cherries[row][left_robot][right_robot] = max_cherries + cherries;
    }
};

References

• Problem

• Discuss

• Solution

Answer 1

Code Review

This initializes all members to zero:

    int map_cherries[70][70][70] = {};

Then you manually initialize the map again:

        std::memset(map_cherries, -1, sizeof(map_cherries));

---

This is not doing what you think it is doing.

        std::memset(map_cherries, -1, sizeof(map_cherries));

This is initializing every byte to -1. Each integer is probably 4 bytes (or more long). So each byte is being set to -1. Now it happens that in 2's compliment this work (if you set all bytes to -1 then the integer is also -1). But there is no guarantee in the standard that C++ will use 2's compliment as the representation of integers (even if it is very common).

---

This returns a const inline int!

    const inline int depth_first_search(
        ...
    )

I know it is legal but come on. That's hard to read. If you have to add inline put it first so we can make the return type readable.

    inline const int depth_first_search(...)

Now we can see that the return type is const int. That still does not make that much sense. Just return the an int.

The inline keyword has no functional use to the C++ compiler (the compiler writers stopped believing developers had a good idea about this years ago). So this keyword has no effect on the code being generated. The only reason it is used is when the function is defined in the header file but not in the class it is needed to let the linker know there may be multiple definitions (as it may have been included multiple times). But when the method is part of the class this is redundant as it is automatically inline.

The general consensus is don't use inline unless you need to use inline. The only time you need to use inline is for method definitions in header files where they are not defined as part of the class.

    int depth_first_search(...)

---

If you don't intend to modify a reference pass it by const reference.

    const inline int depth_first_search(
        std::vector<std::vector<int>> &grid,
         ...
    )

This will prevent mistakes where you accidentally modify the data.

---

Nice short circuit here.

        if (row == row_length) {
            return 0;
        }

But here: Not sure this will ever happen!
Nice optimization. I like it.

        if (map_cherries[row][left_robot][right_robot] != -1) {
            return map_cherries[row][left_robot][right_robot];
        }

It took me a while to spot this as an optimization. I would add a comment on WHY this is working and how this is a shortcut optimization.

---

This if statement is a bit complex. I would split it into a couple of statements.

                if (curr_left_robot > -1 and curr_left_robot < col_length and curr_right_robot > -1 and curr_right_robot < col_length) {


                 // You can do in 1 statement if you want.
                 // But I like the use of a function here as it tells you
                 // what the test is and thus documents the code is doing.
                 if (!inBounds(curr_left_robot)) {
                     continue;
                 }
                 if (!inBounds(curr_right_robot)) {
                     continue;
                 }

---

Sure that's legal.

        return map_cherries[row][left_robot][right_robot] = max_cherries + cherries;

Makes the line very long though.
I would split into three lines;

        // Add cherries in this row to the previous row.            
        cherries += max_cherries;

        map_cherries[row][left_robot][right_robot] = cherries;
        return cherries;