47. Maximum value of a gift

47. Maximum value of a gift

Topic describes

A gift is placed on each square of an M * N board, and each gift has a value (value greater than 0). You can start at the top left of the board and move one space to the right or down until you reach the bottom right of the board. Given the value of a chess board and the gifts on it, calculate the maximum value of gifts you can get.

Example:

,3,1 input: [[1],,5,1 [1], [4, 2, 1]] output: 12: path 1-3-5-2-1, you can get the most value of the giftCopy the code

Tip:

• 0 < grid.length <= 200
• 0 < grid[0].length <= 200

The problem solving process

DFS depth-first searches all paths to the destination

class Solution {
    // The maximum number of gifts
    int res = Integer.MIN_VALUE;
    / / DFS path
    List<Integer> route = new ArrayList<>();
    public int maxValue(int[][] grid) {
        DFS(grid, 0.0);
        return res;

    }
    /** * depth-first search */
    private void DFS(int[][] grid, int i, int j) {
        if (i >= grid.length || j >= grid[0].length) {
            return;
        }
        // Add a gift
        route.add(grid[i][j]);
        // get to the end
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            // Calculate the value of this path
            int routeVal = 0;
            for (Integer e : route) {
                routeVal += e;
            }
            // Select the maximum value of the gift
            res = Math.max(routeVal, res);
        }

        DFS(grid, i, j + 1);
        DFS(grid, i + 1, j);
        // Remove the layer node
        route.remove(route.size() - 1); }}Copy the code

Results:

Time complexity is too high!!

Analyze:

Excluding the edge nodes, each node basically has its successors in two directions. If the number of nodes is N, it is O(2^N). Teacher Ma said, stop! You also include O(N^1/2) addition in time!!

OK, so omit the addition here:

class Solution {
	// The maximum number of gifts
    int res = Integer.MIN_VALUE;
    public int maxValue(int[][] grid) {
        DFS(grid, 0.0.0);
        return res;
    }
    // The sum of paths before val
    private void DFS(int[][] grid, int i, int j, int val) {
        if (i >= grid.length || j >= grid[0].length) {
            return;
        }
        // Add a gift
        val += grid[i][j];
        //
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            res = Math.max(val, res);
        }
        DFS(grid, i, j + 1, val);
        DFS(grid, i + 1, j, val); }}Copy the code

Results:

Analyze:

You can be sure that the time complexity in this case does not allow for order 2 to the N.

Check out the comments section to see what others think!! (Small shame!!)

Yes, dynamic programming, this problem is the same as 70. Climbing stairs!! (Stair climbing is not strictly a dynamic programming problem.)

The state transition equation is as follows:

DP(i,j)=Math.max(DP(i-1,j),DP(i,j-1))+NUM(i,j);

Recursive implementation:

class Solution {
    public int maxValue(int[][] grid) {
        return dp(grid, grid.length - 1, grid[0].length - 1);
    }

    private int dp(int[][] grid, int i, int j) {
        if (i < 0 || j < 0) {
            return 0;
        }
        return Math.max(grid[i][j] + dp(grid, i - 1, j), grid[i][j] + dp(grid, i, j - 1)); }}Copy the code

I can’t say that the code implementation and the stair climbing problem are very similar.

But goose results:

Problem is that there is not to eliminate repeated problems, take the stairs of f (4) = f (3) + f (2), and f (3) = f (2) + f (1),… So f of 2 is computed multiple times.

Iterative method to achieve:

class Solution {
    public int maxValue(int[][] grid) {
        int[][] dpTable = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                 int val=0;
                 if(i-1> =0){
                     val = Math.max(val, dpTable[i - 1][j]);
                 }
                 if(j-1> =0){
                     val = Math.max(val, dpTable[i][j - 1]); } dpTable[i][j]=grid[i][j]+val; }}return dpTable[grid.length - 1][grid[0].length - 1]; }}Copy the code

Results: