本文共 3474 字，大约阅读时间需要 11 分钟。

 思路：

一开始考虑怎么用动态规划解决问题，反而没什么头绪。于是改变思路，先不管动态规划，而是想如何解决这道题。

可以肯定的是，如果s3的最后一个字符与s1和s2的最后一个字符都不同，那么将无法通过s1与s2的交错得到s3。假若s1与s2其中一个的最后一个字符与s3的最后一个字符相同(假设是s1,删除最后一个字符得到s1*，而s3删除最后一个字符得到s3*)。那么问题将转化为s1*,s2与s3*的子问题。不过如果简单地从后往前删除，如果过程中s1、s2、s3的最后一个字符都相同时，选择删除s1或者删除s2的最后一个字符可能产生不同的结果，这里可以采用递归，也可以采用动态规划进行解决。

采用动态规划：

dp[i][j表示s1的前i个字符与s2的前j个字符能否通过交错得到s3的前i+j个字符，为０表示不能，为１表示能。

转换方程：

如果s1的第i个字符与s3的第i+j个字符相同，就执行：

dp[i][j] = dp[i-1][j]

如果s2的第j个字符与s3的第i+j个字符相同，就执行：

dp[i][j] = dp[i][j-1]

这两个操作可以都执行。然后还需要注意边界情况。

代码如下：

bool isInterleave(string s1, string s2, string s3) {    int a = s1.length();    int b = s2.length();    int c = s3.length();    if(a+b != c)        return false;    int dp[a+1][b+1] = {0};    for(int i = 0; i <= a; i++) {        if(s1.substr(0, i) == s3.substr(0, i))            dp[i][0] = 1;        else            dp[i][0] = 0;    }    for(int i = 0; i <= b; i++) {        if(s2.substr(0,i) == s3.substr(0,i))            dp[0][i] = 1;        else            dp[0][i] = 0;    }    for(int i = 1; i <= a; i++)    for(int j = 1; j <= b; j++) {        if(s1[i-1] == s3[i+j-1] && dp[i-1][j] == 1)            dp[i][j] = 1;        if(s2[j-1] == s3[i+j-1] && dp[i][j-1] == 1)            dp[i][j] = 1;    }    return dp[a][b] == 1;}

思路：

首先是想到使用递归的方法，Ｔ*为当前Ｔ删除第一个字符后的字符串，集合S*为S中以T的第一个字符开头直至S的末尾的字符串的集合(例如当T为bbit时, T*为bit, S*为{bbit, bit, it})。也就将原问题化解成T*与S*中的串的子问题，当子问题能成功结束，计数加一。最终的计数即为答案。

但似乎这个递归方法不容易转换为动态规划。换个思路，采用动态规划：

设dp[i][j]表示S的前i个字符组成的字符串中与Ｔ的前j个字符组成的字符串相同的子序列的个数，

则不论如何都有：dp[i][j]　>=  dp[i-1][j] ，当s[i-1] != t[j-1]时取等号。

而如果s[i-1] == t[j-1]，那么还需要在原来的基础上加上dp[i-1][j-1]，这就等价于不使用原来S中的一个值来对应t[j-1]，而是采用s[i-1]这个新的值。

代码如下：

int numDistinct(string s, string t) {    int a = s.length();    int b = t.length();    if(a < b)        return 0;    int dp[a+1][b+1] = {0};    for(int i = 0; i <= b; i++)        dp[0][i] = 0;    for(int i = 0; i <= a; i++)        dp[i][0] = 1;          // dp[0][0] = 1    for(int i = 1; i <= a; i++)    for(int j = 1; j <= b; j++) {        if(i < j) {            dp[i][j] = 0;            continue;        }        if(s[i-1] == t[j-1])            dp[i][j] = dp[i-1][j] + dp[i-1][j-1];        else            dp[i][j] = dp[i-1][j];    }    return dp[a][b];}

思路：

限制了只能进行两次交易，求出所有的增长段，找出最大的两笔交易这种贪心算法并不能得到答案。(当然，如果没有限制交易次数，这样无疑时最优的)。那么考虑使用动态规划的思想：

 dp[i][j]表示在前j+1天中交易i次得到的最大收益。

那么可以分为两种情况：

第j天不交易

dp[i][j] = dp[i][j-1]

第j天交易

dp[i][j] = max(price[j]-price[k]+dp[i-1][k-1])

其中在第k天买入了这支股票

也即

dp[i][j] = max(dp[i][j-1], max(price[j]-price[k]+dp[i-1][k-1]))

代码如下：

int maxProfit(vector
   
    & prices) {    int size = prices.size();    if(size == 0 || size == 1)        return 0;    int dp[3][size] = {0};    for(int i = 0; i <= 2; i++)        dp[i][0] = 0;    for(int i = 0; i < size; i++)        dp[0][i] = 0;    for(int i = 1; i <= 2; i++)    for(int j = 1; j < size; j++) {        int t = 0;        for(int k = 0; k <= j; k++)            t = max(prices[j]-prices[k]+dp[i-1][k], t);        dp[i][j] = max(dp[i][j-1], t);    }    return dp[2][size-1];}
   

然而由于重复计算，最后一个样例会超时，需要优化：

int maxProfit(vector
   
    & prices) {    int size = prices.size();    if(size == 0 || size == 1)        return 0;    int dp[3][size] = {0};    for(int i = 0; i <= 2; i++)        dp[i][0] = 0;    for(int i = 0; i < size; i++)        dp[0][i] = 0;    for(int i = 1; i <= 2; i++) {        int t = prices[0];        for(int j = 1; j < size; j++) {            t = min(t, prices[j]-dp[i-1][j-1]);            dp[i][j] = max(dp[i][j-1], prices[j]-t);        }    }    return dp[2][size-1];}
   

转载地址：http://dwwob.baihongyu.com/