5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

  • 暴力搜索，失败，耗费时间太长。
  • 动态规划，通过。

使用动态规划时首先要找到题目的状态转移方程，以字符串的长度进行增长。

方程： P(i,j) = P(i+1,j-1) && s[i]==s[j] (s是字符串)

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
class Solution {
public:
    bool Is(string s,int st,int len)
    {
        for(int i=0;i<len/2;i++)
        {
            if(s[st+i]!=s[st+len-i-1])
                return false;
        }
        return true;
    }
    string longestPalindrome(string s) {
        int len = s.length();
        int max=-1;
        string res;
        vector<vector<bool>> dp(len,vector<bool>(len));
        for(int l=0;l<len;l++)
        {
            for(int i=0;i+l<len;i++)
            {
                if(l==0)
                {
                    dp[i][i+l]=true;
                }
                else if(l==1)
                {
                    dp[i][i+l]= s[i]==s[i+l];
                }
                else
                {
                    dp[i][i+l] = dp[i+1][i+l-1] && s[i]==s[i+l];
                }
                if(dp[i][i+l] &&l>max)
                {
                    max=l;
                    res=s.substr(i,max+1);
                }
            }
        }
        return res;         
    }
};

32. 最长有效括号

动态规划算法。

1

  • dp[i][j] = n ,代表从i - j 是有效括号字符串 且长度为n。
  • 列出状态转移方程：
    dp[i][j] =
    • if dp[i+1][j-1]>0 && s[i]==’ ( ’ && s[j] ==’ ) ’ then dp[i][j] = dp[i+1][j-1]+2
    • for k = i+1 : j-1
      if s[i][k]>0 && s[k+1][j]>0 then dp[i][j] = dp[i][k]+dp[i+1][j]
  • 编写算法，发现时间复杂度有点高，最后有三个用例时间超时。
  • 总结： 可以发现 n=j-i+1,这就说明，j在此处有些多余，改进时可将j去掉。

2

  • dp[i]=n , 代表截至到 i 的有效括号字符串长度是 n 。
  • 状态转移方程：
    dp[i] = if s[i]==’)’
    • if s[i-1] == ‘(’ then dp[i] = dp[i-2] + 2
    • else if s[i - dict[i-1]-1]==’(’ then dp[i] = dp[i-1] + 2 + dp[i - dict[i-1]-2]
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
class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.length();
        vector<int> dict(len,0);
        int max = 0;
        for(int i=1;i<len;i++)
        {
            if(s[i]==')')
            {
                if(s[i-1]=='(')
                {
                    dict[i] = i>1?dict[i-2]+2:2;
                }
                else if(i - dict[i-1]-1>=0 &&s[i - dict[i-1]-1]=='(')
                {
                    dict[i] = dict[i-1]+2;
                    if(i - dict[i-1]-2>=0 &&dict[i - dict[i-1]-2]>0)
                    {
                        dict[i]+=dict[i - dict[i-1]-2];
                    }
                }
                max = dict[i]>max?dict[i]:max;
            }
        }
        return max;
    }         
};

62. 不同路径

  • 方程：dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]

  • 注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1 ！！！

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 uniquePaths(int m, int n) {
        int *dp = (int *)malloc(sizeof(int)*m*n);
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0||j==0)
                {
                    dp[i*n+j] =1;
                }
                else
                {
                    dp[i*n+j] =dp[i*n+j-n]+dp[i*n+j-1] ;
                }
            }
        }
        return dp[m*n-1];
    }
};

数学方法： 机器人会走 m-1 + n-1 步，其中一定需要向下走 m-1 步，所以有 Cm+n−2m−1C_{m+n-2} ^ {m-1}

64. 最小路径和

  • 类似于62题，唯一的区别就是对于路径增加了权重，从而无法使用数学方法解答了。

  • 方程：dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]

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
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n));

        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0&&j==0)
                {
                    dp[i][j] = grid[i][j];
                }
                else if(i==0)
                {
                    dp[i][j]=dp[i][j-1]+grid[i][j];
                }
                else if(j==0)
                {
                    dp[i][j]=dp[i-1][j]+grid[i][j];
                }
                else
                {
                    dp[i][j]  = min(dp[i-1][j],dp[i][j-1])+grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];

    }
};

121. 买卖股票的最佳时机

  • 方程：dp[i]=max(dp[j]+price[i]−price[j])(j=i−1:0)dp[i] = max(dp[j] + price[i] - price[j]) (j = i-1 : 0)
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) {
        int len =prices.size();
        vector<int> dp(len,0);
        int max = 0;
        for(int i=1;i<len;i++)
        {
            for(int j=i-1;j>=0;j--)
                {
                    if(prices[i]>=prices[j])
                    {
                        dp[i] = dp[j] +prices[i]-prices[j];
                        break;
                    }
                }
            max = max<dp[i]?dp[i]:max;
        }
        return max;

    }
};
  • dp[i]=max(dp[i−1],prices[i]−min)dp[i]=max(dp[i-1],prices[i]-min)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0)
            return 0;
        vector<int> dp(prices.size(),0);
        int _min = prices[0];
        for(int i=1;i<prices.size();i++)
        {
            dp[i] = max(dp[i-1],prices[i]-_min);
            _min = min(_min,prices[i]);
        }   
        return dp[prices.size()-1];
    }
};

198. 打家劫舍

  • 方程 dp[i]=max(dp[i−1],dp[i−2]+nums[i]);dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
  • 本题目中我们不需要全部放的dp数组，所以还可以进行空间优化，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size==0)
            return 0;
        if(size==1)
            return nums[0];
        vector<int> dp(size,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i=2;i<size;i++)
        {
            dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[size-1];
    }
};

338. 比特位计数

  • 主要的是需要找到状态转移函数，其他的就好办了,可以通过观察i分别和 i-1，i/2的关系来找到方程。
  • dp[i]={dp[i−1]+1,ifi mod 2≠0dp[i/2],ifi mod 2=0dp[i]=\begin{cases} dp[i-1] + 1,&{if}&{i \bmod 2} \not={0}\\ dp[i/2],&{if}&{i \bmod 2}={0} \end{cases}
  • 对上述方程还可以进行进一步优化， dp[i]=dp[i/2]+i mod 2dp[i] = dp[i/2] + i\bmod2
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num+1,0);
        for(int i=0;i<=num;i++)
        {
            ret[i] = i&1? ret[i-1]+1:ret[i/2];
        }
        return ret;
    }
};

96. 不同的二叉搜索树

  • 主要还是要找到状态转移函数。
  • 思路是将一个大的树分为两个小的树分别计算，然后左右两边相乘在求和。如n的节点的树，以第1个节点为根节点，分成左边0个节点，右边n-1节点的树，以第2个节点为根节点，分成左边1个节点，右边n-2节点的树，以第3个节点为根节点，分成左边2个节点，右边n-3节点的树。
  • dp[i]=∑j=0i−1dp[j]∗dp[i−1−j]dp[i] = \displaystyle\sum_{j=0}^{i-1} dp[j]*dp[i-1-j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,1);
        for(int i=1;i<=n;i++)
        {
            int sum=0;
            for(int j=0;j<i;j++)
            {
                sum+=dp[j]*dp[i-1-j];
            }
            dp[i] = sum;
        }
        return dp[n];
    }
};

279. 完全平方数

  • 动态规划 dp[i]=min(dp[i−k]+1),k∈sqdp[i] = min(dp[i-k]+1) , k\in sq (sq为平方数的序列)
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 numSquares(int n) {
        vector<int> sq;
        vector<int> dp(n+1);
        for (int i = 1; i * i <= n; i++)
        {
            sq.push_back(i * i);
        }
        for (int i = 1; i < n + 1; i++)
        {
            int _min = i;
            for (int j = 0; j < sq.size() && i - sq[j] >= 0; j++)
            {
                _min = min(_min, dp[i - sq[j]] + 1);
            }
            dp[i] = _min;
        }
        return dp[n];
    }
};

309. 最佳买卖股票时机含冷冻期

  • dp[i]=max{dp[j]+max{prices[i]−prices[k](k=j+2∽i−1)}}(j=0∽i−1)dp[i] = max\{dp[j]+max\{prices[i]-prices[k](k= j+2 \backsim i-1)\}\}(j= 0 \backsim i-1) 时间复杂度O(n2)O(n^2)
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
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2)
            return 0;
        vector<int> dp(prices.size());
        int m1=prices[0];
        m1 = min(m1,prices[1]);
        if(prices.size()>2)
            m1 = min(m1,prices[2]);
        dp[1] = max(0,prices[1]-prices[0]);
        
        for(int i=2;i<prices.size();i++)
        {
            int m = prices[i];
            for(int j=i-2;j>0;j--)
            {
                m = min(m,prices[j+2]);
                dp[i]= max(dp[i],(dp[j]+prices[i]-m));
            }
            dp[i]= max(dp[i],dp[i-1]);
            dp[i]= max(dp[i],prices[i]-m1);
        }   
        return dp[prices.size()-1];
    }
};
  • 另外一种，带有三种状态转换的动态规划，时间复杂度O(n)。见解析