Leetcode 动态规划

发表于 | 分类于

前言

最近做了 Leetcode 一些 Dynamic Programming 相关的题目，记录一下思路和解法。

Leetcode 55. Jump Game

题目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

解题思路1：暴力递归

遍历每一个元素，每一种跳跃可能，若某一遍历达到随后则返回 True. 但是该方法问题在于时间效率太低，最坏情况下要遍历每一种可能。会发生Time Exceeding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def jump_game(self, nums):
        def jump(nums):
            if 0 not in nums:
                return True
            if not nums:
                return True
            elif nums[0] == 0:
                if  len(nums) > 1:
                    return False
                else:
                    return True
            else:
                print(nums)
                c = nums[0]
                if c >= len(nums) - 1:
                    return True
                while c:
                    if jump(nums[c:]):
                        return True
                    else:
                        c -= 1

        if jump(nums):
            return True
        else:
            return False

解题思路2: DP

遍历过程中保存当前元素下可进行跳跃的最大距离，若最大距离小于等于0而还没有达到数组结尾，返回 False

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        l = len(nums)
        max_step= -1
        for i in range(l):
            if max_step - 1 > nums[i]:
                max_step -= 1
            else:
                max_step = nums[i]
            if max_step <= 0 and i != l-1:
                return False
        return True

解题思路3：另一种途径

从后向前，last 记录在哪个位置可以跳到最后。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def canJump(self, nums: 'List[int]') -> 'bool':
        n = len(nums)
        if n==0:
            return False
        last = n-1
        for i in range(n-2, -1, -1):
            # 如果第i能跳到last的位置，i就成为新的last
            if i + nums[i] >= last:
                last = i
        return last==0

Leetcode 62. Unique Paths

问题描述

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

maze img

maze img

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

解题思路 1. 暴力递归法

通过递归遍历每一种可能的走法。但该方法的问题也在于时间复杂度过高，\(O(2^{mn})\)。会导致Time Exceeding

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        def find(m, n):
            if m == 0 and n == 0:
                return True
            elif m < 0 or n < 0:
                return False
            else:
                find(m-1, n)
                find(m, n-1)
        return find(m, n)

解题思路2. DP

思路一是通过自上向下递归，试图找到最优解。我们可以换个思路，是否可以从重点出发，计算它邻近的节点达到它的所有可能路径。所以一个点达到终点的可能路径为与他相邻的右方和下方两点可能路径之和。 -- 杨辉三角

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m <= 0 or n <= 0:
            return 0
        if m == 1 or n == 1:
            return 1
        res = [[1 for _ in range(m)] for _ in range(n)]
        for i in range(1, n):
            for j in range(1, m):
                res[i][j] = res[i-1][j]+res[i][j-1]
        return res[n-1][m-1]

Leetcode 322. Coin Change

题目描述 for 322

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note: You may assume that you have an infinite number of each kind of coin.

解题思路-DP

计算从 0 到 amount 所花费的最少的硬币数。当前 amount 为 n 时，选择 n - c 时的硬币数 + 1 取值最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> res(amount + 1, Max);
        res[0] = 0;
        for(int i =1; i <=amount; i++){
            for(int j=0; j<coins.size(); j++){
                int c = coins[j];
                if (i >= c)
                    res[i] = min(res[i-c] + 1, res[i]);
            }
        }
        return res[amount]>amount?-1:res[amount];
    }
};

进阶思路-递归加减支

基本还是递归的思想，但是增加了减支条件，如果剩下的钱都能被某个最大的 coin 整除，则直接加全部用这个面值硬币的硬币数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:

    int coinChange(vector<int>& coins, int amount) {
        int res = INT_MAX, n = coins.size();
        sort(coins.begin(), coins.end());
        helper(coins, n - 1, amount, 0, res);
        return (res == INT_MAX) ? -1 : res;
    }

    void helper(vector<int>& coins, int start, int target, int cur, int& res) {
        if (start < 0) return;
        if (target % coins[start] == 0) {
            res = min(res, cur + target / coins[start]);
            return;
        }

        for (int i = target / coins[start]; i >= 0; --i) {
            if (cur + i >= res - 1) break;
            helper(coins, start - 1, target - i * coins[start], cur + i, res);
        }
    }
};

Leetcode 300. Longest Increasing Subsequence

问题描述

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

解题思路1-DP

状态设计: dp[i] 代表以 nums[i] 结尾的 LIS 长度。

状态转移: dp[i] = max(dp[i], dp[j]+1) (0<=j<i, a[j]<a[i])

边界处理: dp[i] = 1 (0<=j<n)

时间复杂度: O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp (nums.size(), 1);
        int n = nums.size();
        if (n <= 0) return 0;
        int l = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j < i; j ++){
                if (nums[i] > nums[j]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
            l = max(l, dp[i]);
        }
        return l;
    }
};

进阶思路 贪心+二分查找

第一步中在第二个循环查找插入的子序列时可以优化为二分查找，时间复杂度变为 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> ends{nums[0]};
        for (auto a : nums) {
            if (a < ends[0]) ends[0] = a;
            else if (a > ends.back()) ends.push_back(a);
            else {
                int left = 0, right = ends.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (ends[mid] < a) left = mid + 1;
                    else right = mid;
                }
                ends[right] = a;
            }
        }
        return ends.size();
    }
};

进阶写法 lower_bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> last;
        for (auto num : nums) {
            auto it = lower_bound(last.begin(), last.end(), num);
            if (it == last.end()) {
                last.push_back(num);
            } else {
                *it = num;
            }
        }
        return last.size();
    }
};