动态规划算法练习 (3)

1. 按摩师 (https://leetcode-cn.com/problems/the-masseuse-lcci)

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

这个题目明显就是以前提到的打家劫舍的小偷问题，只不过小偷改行按摩师了。同样是第i次的结果取决于i-1次和i-2次，即dp[i] = max(dp[i-1], dp[i-2] + i)

def massage(nums):
    last = 0
    now = 0
    for i in nums:
        now, last = max(last + i, now), now
    return now

2.不同路径 (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]。

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]