面试推迟了,开学却没有,单进程菜鸡寻思着论文是来不及写了,还是好好学一学DP吧TAT。
就对着LeetCode动态规划专题按顺序刷好了。

1. 最长回文子串

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

样例

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"

代码

$dp[i][j]$为布尔型,表示字符串$s[i...j]$是否为回文串。
初始状态,首先,长度为1的字符串一定是回文串,所以$dp[i][i]$均为true。
其次,可以通过判断$s[i]$与$s[i+1]$是否相等来判断长度为2的子串是否为回文串。
长度为3及以上时,通过状态转移方程$dp[i][j] = dp[i+1][j-1] \& s[i] == s[j]$判断。

WA在两个地方,一是空串忘记判断,二是外层循环len范围可以等于n。
另外还可以记一下s.substr(start, len)的用法。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n == 0) return "";

        int ansi = 0, ansj = 0;
        bool dp[n][n]; memset(dp, false, sizeof(dp));

        // len = 1
        for(int i=0; i<n; i++) dp[i][i] = true;

        // len = 2
        for(int i=0; i<n-1; i++) {
            if(s[i]==s[i+1]) {
                dp[i][i+1] = true;
                ansi = i, ansj = i + 1;
            }
        }

        // len >= 3
        for(int len=3; len<=n; len++) {
            for(int i=0; i<n; i++) {
                int j = i + len - 1;
                if(j >= n) break;
                if(dp[i+1][j-1] && s[i] == s[j]) {
                    dp[i][j] = true;
                    ansi = i, ansj = j;
                }
            }
        }

        return s.substr(ansi, ansj - ansi + 1);
    }
};

2. 正则表达式匹配


3. 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

样例

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

代码

受回文串影响太深,一开始的想法是用DP单独判断"(())"类似于这种多层嵌套的,然后再用一个一维数组a[i]记录以i开头的相邻的已匹配括号长度以求出最长有效括号子串的长度,然后发现"(()())"这种就会被直接漏掉,我太蠢了。
于是我瞄了一眼题解……TAT
$dp[i+1]$表示以$s[i]$结尾的最长有效括号子串的长度,之所以用$dp[i+1]$而非$dp[i]$,是为了腾出$dp[0]=0$防止越界情况,后面也有提到。
这里$dp$数组只有一维,我试想了一下如果第一题回文串也用一维,很明显是不行的。回文串无论是组成还是匹配都相对复杂,括号只有'('')'两种字符,匹配模式也单一。
状态转移方程是关键。分三种情况。
首先我们排除不可能的情况,如果当前位$s[i]$为'(',显然无法更新,直接continue。
第二种情况,当前位$s[i]$是')'并且前一位$s[i-1]$是'(',直接从该对括号之前转移过来,所以就是$dp[i+1]=dp[i-1]+2$。
第三种情况,当前位$s[i]$是')'并且前一位$s[i-1]$也是')'。这个时候如果$s[i-dp[i]-1]$是'(',则需要从两个地方转移。一是前一位$s[i-1]$,即从$dp[i]$转移,即看这一对括号里面是否有已经匹配的子串。二是$s[i-dp[i]-2]$,即$dp[i-dp[i]-1]$,即看加上这一对括号之后,是否与前面的匹配子串相连。综上,$dp[i+1]=dp[i] + 2 + dp[i-dp[i]-1]$。
初始时,$dp[i]=0$,道理显然,懒得写啦。

除了状态转移有点绕以外,就是$dp[i+1]$的问题。一开始写的时候用$dp[i]$表示以$s[i]$结尾的最长有效括号子串的长度,然后发现每一种情况都需要越界的特判,比如说$dp[i+1]=dp[i-1]+2$如果改为$dp[i]=dp[i-2]+2$,在$i=1$时就会出问题,另一种情况同理。

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int dp[n+1]; memset(dp, 0, sizeof(dp));
        int ans = 0;
        for(int i=1; i<n; i++) {
            if(s[i] == '(') continue;
            if(s[i-1] == '(') {
                dp[i+1] = dp[i-1] + 2;
                ans = max(ans, dp[i+1]);
            }
            else {
                if(i-dp[i]-1 < 0) continue;
                if(s[i-dp[i]-1] == '(') {
                    dp[i+1] = dp[i] + 2 + dp[i-dp[i]-1] ; 
                    ans = max(ans, dp[i+1]);
                }
            }
        }
        return ans;
    }
};

晚上和zz视频他!不!会!做!这!道!题!(得意.jpg。
(说得像我会做。


4. 通配符匹配


5. 最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

样例

示例 1:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

代码

其实我感觉我根本没想清楚,就凭感觉写了。
$dp[i]$表示以第$i$位结尾的最长子序列的非负和,注意不是前$i$位的。
我知道这个说法很奇怪,但是确实是这样的。$dp$数组里的数可能不是最值,最值由变量$ans$记录。
如果计算出当前$dp$位的值为负数,说明这之前的子序列不会对后面的子序列有有效的贡献了,所以我把它清零,后面的重新开始计算和。
其实$dp$数组好像根本就不需要开。
然后这道题也用$dp[i+1]$来表示第$i$位的信息,道理同第三题。

WA了一次,原因在于nums可能为负数,原来将ans初始化为0,就错了。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp[n+1]; memset(dp, 0, sizeof(dp));
        int ans = nums[0];
        for(int i=0; i<n; i++) {
            dp[i+1] = dp[i] + nums[i];
            ans = max(ans, dp[i+1]);
            if(dp[i+1] < 0)  dp[i+1] = 0;
        }
        return ans;
    }
};

6. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?

例如,上图是一个7 x 3 的网格。有多少可能的路径?

样例

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

提示

  • m 和 n 的值均不超过 100。

代码

过于简单了,虽然我又WA了一发,做题不带脑子。
$dp[i][j]$表示第$i$行第$j$列的方案数,显然每一个位置可以从上方或左方两个位置转移过来,状态转移方程$dp[i][j] = dp[i][j-1] + dp[i-1][j]$。
初始化第一行第一列均为1即可,其余均为-1,不能到达。

WA的地方在于原来写的$dp[0][0]=0$,我是猪。

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[105][105]; memset(dp, -1, sizeof(dp));
        dp[0][0] = 1;
        for(int i=1; i<m; i++) dp[0][i] = 1;
        for(int i=1; i<n; i++) dp[i][0] = 1;
        for(int i=1; i<n; i++) {
            for(int j=1; j<m; j++) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[n-1][m-1];
    }
};

7. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

样例

示例 1:
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

提示

  • m 和 n 的值均不超过 100。

代码

依然很简单,然而我又WA了。
相比于上一题,无非就是多了一些$dp$值为-1不能转移的情况。
初始化第一行第一列时,如果遇到障碍,暂停该行/列的初始化为1,也就是说,还未初始化的均为-1。
后续转移时,注意判断一下$dp[i-1][j]$和$dp[i][j-1]$的-1情况即可。
最后,$dp[n-1][m-1]$如果为-1,则返回0,否则返回$dp[n-1][m-1]$。

第一次WA,我没有判断如果起点就有障碍物的情况。
第二次WA,居然有一个中间过程会爆int?我认为这不是我的锅orz...

typedef long long LL;
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        LL dp[105][105]; memset(dp, -1, sizeof(dp));
        if(obstacleGrid[0][0] == 1) return 0;
        dp[0][0] = 1;
        for(int i=1; i<m; i++) {
            if(obstacleGrid[0][i] == 1) break;
            dp[0][i] = 1;
        }
        for(int i=1; i<n; i++) {
            if(obstacleGrid[i][0] == 1) break;
            dp[i][0] = 1;
        }
        for(int i=1; i<n; i++) {
            for(int j=1; j<m; j++) {
                if(obstacleGrid[i][j] == 1) continue;
                // cout<<i<<" "<<j<<" "<<dp[i][j-1]<<" "<<dp[i-1][j]<<endl;
                if(dp[i][j-1] == -1 && dp[i-1][j] == -1) continue;
                if(dp[i][j-1] == -1) dp[i][j] = dp[i-1][j];
                else if(dp[i-1][j] == -1) dp[i][j] = dp[i][j-1];
                else dp[i][j] = dp[i][j-1] + dp[i-1][j];
                // cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            }
        }
        if(dp[n-1][m-1] == -1) return 0;
        return dp[n-1][m-1];
    }
};

8. 最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
每次只能向下或者向右移动一步。

样例

示例 1:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

代码

又过于简单了,和上面数路径数的题大同小异。
$dp[i][j]$表示第$i$行第$j$列的路径和,显然每一个位置可以从上方或左方两个位置转移过来,要路径和最小,状态转移方程$dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]$。
初始化第一行第一列为对应的$grid[i][j]$即可。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dp[1005][1005]; memset(dp, -1, sizeof(dp));

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

9. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
给定 n 是一个正整数。

样例

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

代码

这个更简单了,我还有zz给ACM队讲这个的照片,那时候我才大一。
$dp[i]$表示到达第$i$级台阶的方案数。由于每次可以跳一级或两级,所以显然$dp[i]=dp[i-1]+dp[i-2]$。

class Solution {
public:
    int climbStairs(int n) {
        int dp[1000];
        dp[0] = 0; dp[1] = 1; dp[2] = 2;
        for(int i=3; i<=n; i++) dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }
};

10. 编辑距离

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

样例

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

代码

刚做完爬楼梯再做这个感觉自己智商停留在爬楼梯了。
后来了解到这是双序列型动态规划,一般用$dp[i][j]$来表示串$S$处理到第$i$个位置,串$T$处理到第$j$个位置的答案。
对于$dp[i][j]$,可以从三个状态转移过来,状态转移方程$dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1$。
从$dp[i-1][j-1]$转移过来,意味着这一位使用了替换。
从$dp[i-1][j]$转移过来,意味着这一位使用了删除。
从$dp[i][j-1]$转移过来,意味着这一位使用了添加。
然后和规划路径一样(其实仔细想想他们本质上就是一样的),初始化第一行第一列。
这里也用到了$dp$数组下标统一加1的小技巧。

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size(), len2 = word2.size();
        int dp[len1+1][len2+1]; dp[0][0] = 0;
        for(int i=1; i<=len1; i++) dp[i][0] = i;
        for(int i=1; i<=len2; i++) dp[0][i] = i;
        for(int i=0; i<len1; i++) {
            for(int j=0; j<len2; j++) {
                if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j];
                else dp[i+1][j+1] = min(min(dp[i][j], dp[i][j+1]), dp[i+1][j]) + 1;
                // cout<<i+1<<" "<<j+1<<" "<<dp[i][j]<<endl;
            }
            
        }
        return dp[len1][len2];
    }
};

11. 最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

样例

示例 1:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

代码

失败AGAIN。TAT。
一开始的思路是用$dp[i+1][j+1]$表示点$(i,j)$为右下角的最大矩形的面积,然后发现转移不了。
然后看了题解说是上一道题(此上一题非彼上一题)的拓展。于是我先做了上一题。不过后来问了zz说这题还蛮难的……
思路大概是这样。
逐行遍历,对于每一行遍历每一列,用$dp[i]$表示当前第$i$列以该位置结尾的竖着的矩形高度。
对于每一行,可以得到当前遍历完成行的柱状图,于是转化成上一题柱状图中最大的矩形

而柱状图中最大的矩形面积则用单调栈来解决。
构造一个栈,里面存放数组下标,保持下标对应元素单调不减。
遍历数组,当当前元素大于等于栈顶元素时入栈。否则,弹出小于当前元素的所有元素后入栈,入栈前计算弹出元素所能产生的最大面积。
所有元素处理完毕后,依次弹出栈内所有元素,并计算每个元素所能产生的最大面积。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> s; s.push(-1);
        int ans = 0;
        for(int i=0; i<n; i++) {
            if(s.top()!=-1 && heights[s.top()] >= heights[i]) {
                while(s.top()!=-1 && heights[s.top()] > heights[i]) {
                    int x = s.top(); s.pop(); 
                    int y = s.top();
                    ans = max(ans, heights[x] * (i - y - 1));
                }
            }
            s.push(i);
        }
        while(s.top()!=-1) {
            int x = s.top(); s.pop();
            int y = s.top();
            ans = max(ans, heights[x] * (n - y - 1));
        }
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(); if(n == 0) return 0;
        int m = matrix[0].size();
        int ans = 0;
        vector<int> dp(m, 0);
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
            ans = max(ans, largestRectangleArea(dp));
        }
        return ans;
    }
};

12. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码:
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。

样例

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

代码

和爬楼梯有些类似,但被关于$0$的特殊情况搞死……
如果$s[i]==0$,分为两种情况。一是$s[i-1]==1$或*$s[i-1]==2$,这个$0$被组合解释为$10$或$20$,那么$dp[i]=dp[i-2]$;二是$s[i-1]$不为$1$或$2$,那么这个$0$既无法与前面一位非$1$和$2$的数字相连解释,也无法和后一位连成$0x$被解释,所以整个串无法被解释,返回$0$。
如果$s[i]!=0$,如果第$i$位和第$i-1$位组成的数字满足在范围$[1,26]$内的话,那么$dp[i]$既可以从$dp[i-2]$转移过来,即第$i-1$位和第$i$位被组合解码;或者$dp[i]$从$dp[i-1]$转移过来,即第$i$位单独解码。所以$dp[i]=dp[i-1]+dp[i-2]$。否则,如果第$i$位和第$i-1$位组成的数字满足不在范围$[1,26]$内,那么第$i$位只能被单独解码,所以$dp[i]=dp[i-1]$。
最后要处理的是边界条件。如果$s[0]==0$,那么$dp[0]=0$;如果$s[0]!=0$,那么$dp[0]=1$。
为了防止越界,将$dp$数组下标统一加一处理,$dp[0]=1$,别问我为什么。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        
        int dp[n+1]; 

        dp[0] = 1;
        dp[1] = (s[0] == '0' ? 0 : 1);
        if(n == 1) return dp[1];
        
        for(int i=1; i<n; i++) {
            if(s[i] == '0') {
                if(s[i-1] == '1' || s[i-1] == '2') dp[i+1] = dp[i-1];
                else return 0;
            }
            else {
                if(s[i-1] == '1' || (s[i-1] == '2' && s[i] >= '1' && s[i] <='6')) dp[i+1] = dp[i] + dp[i-1];
                else dp[i+1] = dp[i];
            }
        }
        return dp[n];
    }
};

13. 不同的二叉搜索树

给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?

样例

示例 1:

输入: 3
输出: 5

代码

二叉搜索树就是中序遍历是排列顺序的树,那么考虑根,会发现这是一个卡特兰数列。
假设$1 ... n$组成的二叉搜索树的数量为$f(n)$,那么$f(n)=g(1)+g(2)+...+g(n)$,其中$g(x)$为以$x$为根的组成$1...n$的二叉搜索树数量。其左边有$x-1$个数,可以构建$f(x-1)$种二叉搜索树;右边有$n-x$个数,可以构建$f(n-x)$种二叉搜索树。
所以,显然易见,$f(n)=\sum_{i=1}^{n}f(i-1)f(n-i)$。

class Solution {
public:
    int numTrees(int n) {
        int dp[n+1]; memset(dp, 0, sizeof(dp));
        dp[0] = 1; dp[1] = 1; 
        for(int i=2; i<=n; i++) {
            for(int j=1; j<=i; j++) 
                dp[i] += dp[j-1] * dp[i-j];
        }
        return dp[n];
    }
};
最后修改:2020 年 03 月 04 日 05 : 13 PM
如果觉得我的文章对你有用,请随意赞赏