题目
剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例：
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 复制代码
分析
本题主要思路是利用动态规划将每个格子的最大值计算出来
需要注意的是对各种边界情况的处理
- 定义 dp 数组
dp[i][j] 表示i行j列可取的最大值
- 写出dp数组状态转移方程
dp[i][j] = max{dp[i-1][j], dp[i][j-1]} + grid[i][j]
- 初始化dp数组
dp[0][0] = grid[0][0]
迭代求解 dp 数组
分析边界情况，先求出边界，在求出内部
- 第一行的最大值只能由第一行遍历过去求得
- 第一列的最大值只能由第一列遍历过去求得
- 内部的按行或者按列逐层遍历得到即可
- 返回结果
实现
function maxValue(grid: number[][]): number { let m = grid.length // 行 let n = grid[0].length // 列 let dp = new Array(m) for (let i = 0; i < dp.length; i ++) { dp[i] = new Array(n) } dp[0][0] = grid[0][0] // 计算边界 行 for (let i = 1; i < m; i ++) { dp[i][0] = dp[i - 1][0] + grid[i][0] } // 计算边界 列 for (let j = 1; j < n; j ++) { dp[0][j] = dp[0][j - 1] + grid[0][j] } // 计算除边界 遍历 for (let i = 1; i < m; i ++) { for (let j = 1; j < n; j ++) { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j] } } return dp[m-1][n-1] }; 复制代码
题目
剑指 Offer 46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例：
输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" 复制代码
分析
这道题分析到最后与青蛙跳台阶有点类似，只是在每一次求解时都需要格外判断一下是否可以跳
- 定义 dp 数组
dp[i] 以第 i 个字母结尾有几种不同方法
- 写出状态转移方程
dp[i] = dp[i-1] 当结尾两个字母相连无法解析成其它字母时dp[i] = dp[i-1] + dp[i-2]当结尾两个字母可以解析成其它字母时，说明最终结果可以由前两种状态得到
- 初始化dp数组
dp[0] = 1 dp[1] = 判断是否满足连子翻译条件，是为2，否为1
- 迭代求解 dp 数组
实现
function translateNum(num: number): number { // dp[i] 以第 i 个字母结尾有几种不同方法 let str = num.toString() let len = str.length let dp = [] dp[0] = 1 let i = 1 while(i < len) { let cur = + (str[i - 1] + str[i]) if (cur >= 10 && cur <=25) { if ( i == 1) { dp[i] = 2 } else { dp[i] = dp[i - 1] + dp[i - 2] } } else { dp[i] = dp[i - 1] } i ++ } return dp[len - 1] };
