# 47、礼物的最大价值 题目 在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？ 思想 动态规划：values[i][j] = sum + Max( values[i-1][j] , values[i][j-1]) ``` // 在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。 // 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。 // 给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？ let gifts = [ [1, 10, 3, 8], [12, 2, 9, 6], [5, 7, 4, 11], [7, 7, 16, 5] ] console.log(getMaxValue(gifts)) // 53 function getMaxValue(gifts) { let sum = 0 let i = 0 let j = 0 while (i < gifts.length && j < gifts[0].length) { if (i === gifts.length - 1) { while (j < gifts[0].length) { sum += gifts[i][j] j++ } break } else if (j === gifts.length - 1) { while (i < gifts.length) { sum += gifts[i][j] i++ } break } else { sum += gifts[i][j] if (sum + gifts[i+1][j] < sum + gifts[i][j+1]) { j++ } else { i++ } } } return sum } ```