題目描述：在一個 m*n 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0）恨旱。你可以從棋盤的左上角開始拿格子里的禮物辈毯，并每次向右或者向下移動一格、直到到達棋盤的右下角搜贤。給定一個棋盤及其上面的禮物的價值谆沃，請計算你最多能拿到多少價值的禮物？
解法：動態(tài)規(guī)劃
聲明狀態(tài)數(shù)組dp是一個 m*n 的二維數(shù)組仪芒。dp[i][j]的默認值是 0唁影，它的含義是：在坐標點（i，j）處掂名，能得到的最大價值禮物据沈。所以，整個棋盤的最大價值禮物就是 dp[m-1][n-1] 的值饺蔑。
現(xiàn)在來看狀態(tài)轉移的過程：
- 出發(fā)點是左上角锌介，且只能向右/下移動，所以第一列和第一行中的 dp 值猾警，就等于：當前禮物價值+上一個 dp 值
- 對于一般坐標（i孔祸，j），
dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1])
代碼實現(xiàn)如下：
// ac地址：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
// 原文地址：https://xxoo521.com/2020-03-11-max-value-of-gift/
/**
* @param {number[][]} grid
* @return {number}
*/
var maxValue = function(grid) {
const rowNum = grid.length;
const colNum = grid[0].length;
const dp = [];
for (let i = 0; i < rowNum; ++i) {
dp[i] = [];
for (let j = 0; j < colNum; ++j) {
dp[i][j] = 0;
}
}
dp[0][0] = grid[0][0];
for (let i = 1; i < rowNum; ++i) {
dp[i][0] = grid[i][0] + dp[i - 1][0];
}
for (let j = 1; j < colNum; ++j) {
dp[0][j] = grid[0][j] + dp[0][j - 1];
}
for (let i = 1; i < rowNum; ++i) {
for (let j = 1; j < colNum; ++j) {
dp[i][j] = grid[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[rowNum - 1][colNum - 1];
};
時間復雜度和空間復雜度都是发皿。在 leetcode 上顯示崔慧，內存擊敗 100%，時間擊敗 96.63%：
image
更多資料
整理不易穴墅，若對您有幫助尊浪，請給個「關注+點贊」，您的支持是我更新的動力 ??
- ??Blog：劍指 Offer 題解 + JS 代碼
- ??Github ：https://github.com/dongyuanxin/blog
- ?? 公眾號：心譚博客
