dynamic programming例题

发表于   |   分类于

Index

1
2
3
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock II
Longest Increasing Subsequence

http://www.cnblogs.com/wuyuegb2312/p/3281264.html

1. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

假设 f[i] 为到第 i 天为止可以拿到的最大利润。对于第 i 天，有两种选择，即在当天卖掉股票，或者在第 i 天之前已经卖掉了。那么 f[i] 就是这两种选择中的最大值。如果在第 i 天卖掉股票，那么问题就是在哪天买股票，只要维护一个到第 i 天为止股价的最小值 minPrice 就可以了，此时 f[i] = prices[i] - minPrice ；如果在第 i 天股票已经卖出，则 f[i] = f[i-1] (类似于背包问题，两种选择，卖还是不卖)。综上所述，令 f[i] 表示到第 i 天为止可以拿到的最大利润。状态转移方程为 f[i] = max(f[i-1], prices[i] - minPrice) ，其中 minPrice 表示到第 i 天为止的最低股价，并且有 minPrice = min(minPrice, prices[i]) 。边界条件为 f[0] = 0, minPrice = prices[0] 。最终结果为 f[n-1] 。时间复杂度与空间复杂度均为 O(n) 。

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() <= 1){
            return 0;
        }
        
        int minP = prices[0];
        int profit = prices[1] - prices[0];
        
        for(int i = 2; i < prices.size(); i++){
            minP = min(prices[i - 1], minP);
            profit = max(profit, prices[i] - minP);
        }
        
        if(profit < 0){
            return 0;
        }
        
        return profit;
    }
};

2. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

由于可以无限次买卖，上次的状态模型显然不能用了。考虑第 i 天的行为可以是买入、卖出，或什么都不做。如果要买入，显然至少在第 i-1 天的时候手中是没有持有股票的，而如果要卖出，则至少在第 i-1 天的时候手中必须持有股票，如果什么都不做，则没有限制。根据这样的分析，我们可以知道为了计算第 i 天的情况，我们（只）需要第 i-1 天时持有和未持有股票的情况。据此可以抽象出状态。令 hold[i] 表示第 i 天时持有股票可以获得的最大利润， free[i] 表示第 i 天时未持有股票能获得的最大利润。第 i 天持有股票有两种情况，即第 i-1 天就已经持有，或在第 i 天买入。即 hold[i] = max(hold[i-1], free[i-1] - prices[i]) 。同理第 i 天未持有股票也有对应两种情况，即第 i-1 天未持有，或第 i 天卖出。即 free[i] = max(free[i-1], hold[i-1] + prices[i]) 。初始条件为 hold[0] = -prices[0], free[0] = 0 。最终结果为 free[n-1] 。时间复杂度和空间复杂度均为 O(n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //本题也可以做是最大m 子段和
        int sum = 0;
        for(int i = 1; i < prices.size(); i++){
            int diff = prices[i] - prices[i - 1];
            if(diff > 0){
                sum += diff;
            }
        }
        return sum;
    }
};

3. Longest Increasing Subsequence

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

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?
最长单调递增自序列，有nlog(n)算法，思考过程类似于背包问题，此题中背包不必装满，但是比i(背包容量)小的数j(宝石)，判断max(dp[j]+1, dp[i])，dp[]为子序列个数，相当于背包问题中宝石价值。但是背包问题中，背包捡起一次宝石，背包容量会减小，所以在状态转移方程为max(dp[i - vj(重量)] + 价值，dp[i])，而这个问题不存在背包容量问题，只需要判断j比i小就行了。除此之外还要排出i左边的坑，比如nums[10, 9, 2, 5, 3, 7, 101, 18]中nums[4] = 7，比7小的有[2, 5, 3]，但是子序列要把3这个坑去掉，所以才用max(dp[j] + 1)，解释一下比如i取7的位置，j取3的位置，此时dp[i] = 2，因为有2和5，但是dp[j] ＝ 1，只有2比3小，这时候就跳过3这个数。因为dp[i]是i左边小于nums[i]，并且递增的总和，如果前面有个坑，这个总数会比坑左面的数值小。因此取max(dp[j] + 1)。这个方法经常用，要记住。一般复杂度为O(n^2)。

再说nlog(n)解法，考虑两个数a[x]和a[y]，x<y且a[x]<a[y],且dp[x]=dp[y]，当a[t]要选择时，到底取哪一个构成最优的呢？显然选取a[x]更有潜力，因为可能存在a[x]<a[z]<a[y]，这样a[t]可以获得更优的值。在这里给我们一个启示，当dp[t]一样时，尽量选择更小的a[x].按dp[t]=k来分类，只需保留dp[t]=k的所有a[t]中的最小值，设d[k]记录这个值，d[k]=min{a[t],dp[t]=k}。
这时注意到d的两个特点（重要）：

  1. d[k]在计算过程中单调不升；
  2. d数组是有序的，d[1]<d[2]<..d[n]。
    利用这两个性质，可以很方便的求解：
  3. 设当前已求出的最长上升子序列的长度为len（初始时为1），每次读入一个新元素x：
  4. 若x>d[len]，则直接加入到d的末尾，且len++；（利用性质2）
    否则，在d中二分查找，找到第一个比x小的数d[k]，并d[k+1]=x，在这里x<=d[k+1]一定成立（性质1,2）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    O(n^2)
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n=nums.size();
            if(!n) return 0;
            int result=1;
            vector<int> dp(n,1);
            
            for(int i=1;i<n;i++){
                int temp=0;
                for(int j=0;j<i;j++){
                    if(nums[j]<nums[i]) temp=max(temp,dp[j]);
                }
                dp[i]=temp+1;
                result=max(dp[i],result);
            }
            return result;
        }
    };
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// C++ implementation to find longest increasing subsequence
// in O(n Log n) time.
#include <bits/stdc++.h>
using namespace std;
 
// Binary search
int GetCeilIndex(int arr[], vector<int> &T, int l, int r,
                 int key)
{
    while (r - l > 1)
    {
        int m = l + (r - l)/2;
        if (arr[T[m]] >= key)
            r = m;
        else
            l = m;
    }
 
    return r;
}
 
int LongestIncreasingSubsequence(int arr[], int n)
{
    // Add boundary case, when array n is zero
    // Depend on smart pointers
 
    vector<int> tailIndices(n, 0); // Initialized with 0 
    vector<int> prevIndices(n, -1); // initialized with -1
 
    int len = 1; // it will always point to empty location
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[tailIndices[0]])
        {
            // new smallest value
            tailIndices[0] = i;
        }
        else if (arr[i] > arr[tailIndices[len-1]])
        {
            // arr[i] wants to extend largest subsequence
            prevIndices[i] = tailIndices[len-1];
            tailIndices[len++] = i;
        }
        else
        {
            // arr[i] wants to be a potential condidate of
            // future subsequence
            // It will replace ceil value in tailIndices
            int pos = GetCeilIndex(arr, tailIndices, -1,
                                   len-1, arr[i]);
 
            prevIndices[i] = tailIndices[pos-1];
            tailIndices[pos] = i;
        }
    }
 
    cout << "LIS of given input" << endl;
    for (int i = tailIndices[len-1]; i >= 0; i = prevIndices[i])
        cout << arr[i] << " ";
    cout << endl;
 
    return len;
}
 
int main()
{
    int arr[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
    int n = sizeof(arr)/sizeof(arr[0]);
 
    printf("LIS size %d\n", LongestIncreasingSubsequence(arr, n));
 
    return 0;
}