剑指offer Dynamic Programming

剑指offer-礼物的最大价值

Posted by franki on May 12, 2021

礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

思路

根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。

使用动态规划

动态转移方程

f(i,j)=max[f(i,j−1),f(i−1,j)]+grid(i,j)

f[i][j]

  • i=0, j=0 起始元素
  • i=0, j!=0 f[i][j-1] 矩阵第一行元素，只能从左边走过来
  • i!=0, j=0 f[i-1][j] 矩阵第一列元素，只能从上面走下来
  • i!=0 j!=0 Math.max(f[i][j-1], f[i-1][j]) 可从左边后者下边到达

代码

function maxValue(grid) {
    if (!grid) return null;
    const rows = grid.length;
    const columns = grid[0].length;

    for (let i=0; i<rows; i++) {
        for (let j=0; j<columns; j++) {
            if (i === 0 && j === 0) {
                continue;
            } else if (i === 0) { // 只能向左走
                grid[i][j] += grid[i][j-1];
            } else if (j === 0) { // 只能向上走
                grid[i][j] += grid[i-1][j];
            } else {
                grid[i][j] += Math.max(grid[i][j-1], grid[i-1][j]);
            }
        }
    }

    return grid[rows-1][columns-1];
}

复杂度分析

  • 时间复杂度: O(MN)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS