1. 按摩师 (https://leetcode-cn.com/problems/the-masseuse-lcci)
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
这个题目明显就是以前提到的打家劫舍的小偷问题，只不过小偷改行按摩师了。同样是第i次的结果取决于i-1次和i-2次，即dp[i] = max(dp[i-1], dp[i-2] i)
代码语言：javascript复制def massage(nums):
last = 0
now = 0
for i in nums:
now, last = max(last i, now), now
return now2.不同路径 (https://leetcode-cn.com/problems/unique-paths/)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
根据题目，可以知道当网格为1 x N或者N x 1的时候，路径都是一种。到这里，其实能感受出来，这个题目简直就是全局比对算法中的分数矩阵计算简化版，除了这个题目不能斜着走并且没有计算分数大小。 其中到第 i 行 j 列的格子的方法数，肯定是从左侧的格子和上边的格子而来，也就是第 i - 1行 j 列的方法数与第 i 行 j - 1 列的方法数的和。即dp[i][j] = dp[i - 1][j] dp[i][j - 1]。
代码语言：javascript复制def uniquePaths(m, n):
dp = [[0 for x in range(m)] for y in range(n)]
for x in range(n):
dp[x][0] = 1
for y in range(m):
dp[0][y] = 1
for i in range(1, n):
for j in range(1, m):
dp[i][j] = dp[i - 1][j] dp[i][j - 1]
return dp[-1][-1]
