Celery's Blog

0%

LeetCode-Day34

发表于 Valine：

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

1
2
3
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

方法一. O(n2)O(n^2)

思路：

令dp[i]数组为以第i个元素结尾的最长上升子序列的长度。

dp[j]可以从0-j - 1遍历，然后分别检验nums[j]可以附加到哪个子序列上面，记录maxSum

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

方法二. 动态规划+二分查找 O(nlogn)O(nlogn)

思路：

  • 新的状态定义：我们考虑维护一个列表tails，其中每个元素tails[k]的值代表长度为k + 1的子序列尾部元素的值

  • 状态转移设计：遍历计算每个tails[k]，不断更新长度为[1, k]的子序列尾部元素值，始终保持每个尾部元素值最小（例如 [1,5,3]， 遍历到元素 55 时，长度为 22 的子序列尾部元素值为 55；当遍历到元素 33 时，尾部元素值应更新至 33，因为 33 遇到比它大的数字的几率更大）。

  • tails列表一定是严格递增的：即当尽可能使每个子序列尾部元素值最小的前提下，子序列越长，其序列尾部元素值一定更大

举个例子：

nums = [10, 9, 2, 5, 3, 7, 21, 18]

1. tails = [10]

2. tails = [9]

3. tails = [2]

4. tails = [2, 5]

5. tails = [2, 3]

6. tails = [2, 3, 7]

7. tails = [2, 3, 7, 21]

8. tails = [2, 3, 7, 18]

所以最终长度为4

最后，上Code然后理解一下吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lengthOfLIS(vector<int>& nums) {
    if(nums.size() < 2) {
        return nums.size();
    }
    int tails[nums.size()] = {0};
    int res = 0;
    for(int num : nums) {
        int i = 0, j = res;
        while(i < j) {
            int mid = (i + j) / 2;
            if(tails[mid] < num) {
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        tails[i] = num;
        if(j == res) {
            res++;
        }
    }
    return res;
}

股票问题整理（这里主要介绍动态转移方程，没有进行空间优化）

1. 最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获得的最大利润。

所以，动态转移方程为：

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

dp[i][1] = max(dp[i - 1][1], -prices[i]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) {
            return 0;
        }
        int n = prices.size();
        int dp[n][2];
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for(int i = 1;i < n;i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], -prices[i]);
        }
        return dp[n - 1][0];
    }
};
2. 尽可能地完成更多的交易获取最大的利润（其实就是不限制交易次数）

所以，动态转移方程为：

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(vector<int>& prices) {
    if(prices.size() == 0) {
        return 0;
    }
    int n = prices.size();
    int dp[n][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for(int i = 0;i < n;i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
}
3. 最多只能完成两笔交易

这里需要注意的是枚举k

所以，动态转移方程为：

dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])

dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) {
            return 0;
        }
        int n = prices.size(), max_k = 2;
        int dp[n][max_k + 1][2] = {{{0}}}; 
        for(int i = 0;i < n;i++) {
            for(int k = max_k; k >= 1;k--) {
                if(i == 0) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][max_k][0];
    }
};
4. 含冷冻期（即卖完股票的下一天不能买股票，必须过一天之后才能买股票）

注意，这里画一个状态机会比较好解释

0状态表示可以买股票状态，1状态表示手上有股票，2表示刚刚卖出股票

所以0状态可以通过买股票到达1状态，也可以啥都不干仍停留在原状态

1状态可以啥也不干留在原状态，也可以卖掉股票到达2状态

2状态只能选择射也不做达到0状态（表示冷冻期）

所以，动态规划方程如下：

dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]);

dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

dp[i][2] = dp[i - 1][1] + prices[i];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0) {
            return 0;
        }
        int dp[n][3] = {{0}};
        dp[0][0] = 0, dp[0][1] = -prices[0], dp[0][2] = 0;
        for(int i = 1;i < n;i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = dp[i - 1][1] + prices[i];
        }
        return max(dp[n - 1][2], dp[n - 1][0]);
    }
};
5. 指定完成k笔交易
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxProfit_k(vector<int>& prices, int max_k) {
    int n = prices.size();
    if(max_k > n / 2) {
        return 0;
    }
    int dp[n][max_k + 1][2] = {{{0}}};
    for(int i = 0;i < n;i++) {
        for(int k = max_k;k >= 1;k--) {
            if(i == 0) {
                dp[i][k][0] = 0;
                dp[i][k][1] = -prices[i];
                continue;
            }
            dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
            dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
        }
    }
    return dp[n - 1][max_k][0];
}
6. 含手续费
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if(n == 0) {
            return 0;
        }
        int dp[n][2];
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for(int i = 1;i < n;i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
};

然后滚去看论文了…

没去实验室还被批斗了…惨兮兮.jpg