Sep.20-23 【dp】出租车的最大盈利（中等）& 礼物的最大价值（中等） & 把数字翻译成字符串（中等）

2008. 出租车的最大盈利

提示：

• 1 <= n <= 105
• 1 <= rides.length <= 3 * 104
• rides[i].length == 3
• 1 <= starti < endi <= n
• 1 <= tipi <= 105

定义 d p [ i ] dp[i] dp[i] 表示行驶到 i i i 时的最大盈利。考虑状态转移，一方面，我们可以不接终点为 i i i 的乘客，这样有 d p [ i ] = d p [ i − 1 ] dp[i] = dp[i-1] dp[i]=dp[i−1]；另一方面，我们可以接所有终点为 i i i 的乘客中收益最大的，这样有 d p [ i ] = m a x ( d p [ s t a r t ] + e n d − s t a r t + t i p ) dp[i] = max (dp[start]+end-start+tip) dp[i]=max(dp[start]+end−start+tip)，二者取最大值。最终答案为 d p [ − 1 ] dp[-1] dp[−1]。

# python3
class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        end_dic = dict()
        dp = [0] * n
        for start, end, tip in rides:
            start -= 1
            end -= 1
            if end not in end_dic:
                end_dic[end] = [[start, tip]]
            else:
                end_dic[end].append([start, tip])
        for i in range(1, n):
            dp[i] = dp[i-1]
            for start, tip in end_dic.get(i, list()):
                dp[i] = max(dp[i], dp[start] + i - start + tip)
        return dp[-1]

剑指 Offer 47. 礼物的最大价值

本题的解题关键是：当移动时，某单元格只可能从上边单元格或左边单元格到达。

# python3
class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0:
                    if j > 0:
                        grid[i][j] += grid[i][j-1]
                elif j == 0:
                    grid[i][j] += grid[i-1][j]
                else:
                    grid[i][j] += max(grid[i][j-1], grid[i-1][j])
        return grid[-1][-1]

剑指 Offer 46. 把数字翻译成字符串

可以把这题看做增加条件的爬楼梯问题。

记数字 num 第 i i i 位数字为 x i x_i xi​，数字 num 的位数为 n；
例如： n u m = 12258 num = 12258 num=12258, x 1 = 1 x_1 = 1 x1​=1

• 状态定义： 设动态规划列表 d p dp dp ， d p [ i ] dp[i] dp[i] 代表以 x i x_i xi​ 为结尾的数字的翻译方案数量。

• 转移方程： 若 x i x_i xi​和 x i − 1 x_{i-1} xi−1​，组成的两位数字可以被翻译，则 d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i - 1] + dp[i - 2] dp[i]=dp[i−1]+dp[i−2]；否则 d p [ i ] = d p [ i − 1 ] dp[i] = dp[i - 1] dp[i]=dp[i−1]。

可被翻译的两位数区间：当 x i − 1 = 0 x_{i-1} = 0 xi−1​=0时，组成的两位数是无法被翻译的（例如 00, 01, 02,⋯ ），因此区间为 [10, 25]。

• 初始状态： d p [ 0 ] = d p [ 1 ] = 1 dp[0] = dp[1] = 1 dp[0]=dp[1]=1，即 “无数字” 和 “第 1 位数字” 的翻译方法数量均为 1 ；

• 返回值： d p [ − 1 ] dp[-1] dp[−1]，即此数字的翻译方案数量。

# python3
class Solution:
    def translateNum(self, num: int) -> int:
        s= str(num)
        l = len(s)
        if l < 2:
            return l
        dp = [0] * (l + 1)
        dp[0] = dp[1] = 1
        for i in range(2, l+1):
            if '10' <= s[i-2:i] <= '25':
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]
        return dp[-1]

jyd