[剑指Offer] Day 9: Dynamic Programming

Authored by Tony Feng

Created on April 20th, 2022

Last Modified on April 20th, 2022

Task 1 - Q42. 连续子数组的最大和

Question

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。

Solution

1
2
3
4
5
6
7
8
9


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        tmp = float('-inf')
        maxSum = float('-inf')
        for num in nums:
            tmp = max(tmp + num, num) # It chooses whether to extend the sub-array or restart from the new item.
            maxSum = max(maxSum, tmp) # It records the max value after an array has been updated.

        return maxSum

Explanation

Time Complexity: O(N)
Space Complexity: O(1)

Task 2 - Q47. 礼物的最大价值

Question

在一个 m * n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid: return 0

        dp = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if i == j == 0:
                    dp[i][j] = grid[i][j]
                elif i - 1 < 0:
                    dp[i][j] = dp[i][j-1] + grid[i][j]
                elif j - 1 < 0:
                    dp[i][j] = dp[i-1][j] + grid[i][j]
                else:
                    dp[i][j] = grid[i][j] + max(dp[i][j-1], dp[i-1][j])

        return dp[-1][-1]

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution: # Space Optimization
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid: return 0

        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if i == j == 0: 
                    continue
                elif i - 1 < 0:
                    grid[i][j] += grid[i][j-1]
                elif j - 1 < 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]

Explanation

Solution 2 is an optimized version of solution 1 in the spatial dimension.
Time Complexity: O(N)
Space Complexity
- Solution 1: O(N)
- Solution 2: O(1)