DP-Medium

2020-02-28
Abstract：更新部分Medium难度DP相关题解

63. Unique Paths II

image-20200228211822543

解法一：DP

这道题和Unique Path 1几乎相同，唯一的区别是，当某一格是障碍物时，uniquePath=0，即转移方程为

dp[i][j]=(obstacleGrid[i-1][j-1]==1)?0:  //如果有障碍物直接为0
    (i==1&j==1)?1:                       //起始为1
    dp[i-1][j]+dp[i][j-1];               //取左和上方格子之和

完整解法如下

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid==null || obstacleGrid.length==0)return 0; //特殊情况
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][] dp=new int[m+1][n+1]; //数组开大一圈作为辅助，这样可以避免边界判断
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                dp[i][j]=(obstacleGrid[i-1][j-1]==1)?0:
                (i==1&j==1)?1:
                dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n]; //dp[m][n]即为最终结果
    }
}

​

64. Minimum Path Sum

image-20200228222649924

解法一：DP（不需要额外空间）

和上题还是类似的思路，但是注意上边界和左边界上的值比较坑，需要特别地初始化

需要注意的是，如果使用辅助空间，那么辅助格子和grid上的状态转移方程不能统一！！

因此我这里先对边界值特殊处理，以避免后续麻烦的多重判断

class Solution {
    public int minPathSum(int[][] grid) {
        //if(grid.length==0)return 0;
        int m=grid.length,n=grid[0].length;
        for(int i=1;i<m;i++)grid[i][0]+=grid[i-1][0]; //只有一条路可走
        for(int i=1;i<n;i++)grid[0][i]+=grid[0][i-1]; //同上
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]); //更新最小路径
            }
        }
        return grid[m-1][n-1];
    }
}

​

⭐️5. Longest Palindromic Substring

image-20200229205630824

解法一：中心扩展（其实就是DP嘛）

  • 思路：对于形如“aba”或“baab”的字符串我们可以通过左右+1的操作来复用之前的计算结果，即

    dp(i,j)=(dp(i-1,j+1) && s.charAt(i)==s.charAt(j));

  • 要点：注意分开讨论奇偶长度回文，目的是为了统一寻找回文的标准，如果“abba”当成奇数长串去处理的话就出大麻烦了，另外要注意的是，得到最大回文长度后，如何通过中心元素位置，计算出start和end

    //假设max为最大回文长度
len=max-1;
start=i-(len-1)/2;
end=i+len/2;

  • 完整解法如下

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<=1)return s;
        int start=0,end=0;
        for(int i=0;i<s.length();i++){
            int max=Math.max(centerExpand(s,i,i),centerExpand(s,i,i+1)); //两种中心
            if(max>end-start){
                start=i-(max-1)/2;
                end=i+max/2;
            }
        }
        return s.substring(start,end+1);
    }

    public int centerExpand(String s,int lo,int hi){ //用来找到某一中心的最长回文串
        while(lo>=0 && hi<s.length() && s.charAt(lo)==s.charAt(hi)){lo--;hi++;}
        return hi-lo-1;
    }
}

解法二：Manacher 算法

非常精巧的算法，时间复杂度O(n)，等好好消化理解了再贴上来

​

⭐️91. Decode Ways

image-20200229234943330

解法一：DP

比较要求细心的一道题，必须关注以下几种特殊情况：

  • 当出现诸如"30","40"等时，解码失败，直接return 0

  • "10"和"20"只能记一种，因为“0”无法解码

  • 其余1-26之间的数，和前一次结果叠加，相当于 “xxxab” + “xxxxb” 的结果

class Solution {
    public int numDecodings(String s) {
        if( s.charAt(0)=='0') return 0;
        int pre=1,curr=1;
        for(int i=1;i<s.length();i++){
            int tmp = curr;
            if (s.charAt(i) == '0')
                if (s.charAt(i-1) == '1' || s.charAt(i-1) == '2') curr = pre;
            else return 0;
            else if (s.charAt(i-1) == '1' || s.charAt(i-1) == '2' && s.charAt(i) >= '1' && s.charAt(i) <= '6')
                curr = curr + pre;
            pre = tmp;
        }
        return curr;
    }
}

139. Word Break

image-20200301221358648

  • 要点：用HashSet来判断是否在字典中存在

解法一：记忆化递归

  • 思路：可以分割为两个子串，左边必定是其中一个单词（如果找不到，说明不存在），接着递归求解右子串
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreakWithMemo(s,new HashSet<String>(wordDict),0,new Boolean[s.length()]);
    }

    public boolean wordBreakWithMemo(String s,Set<String> set,int start,Boolean[] memo){
        if(start==s.length())return true;
        if(memo[start]!=null)return memo[start];
        for(int i=start;i<=s.length();i++){
            if(set.contains(s.substring(start,i)) && wordBreakWithMemo(s,set,i,memo))
                return memo[start]=true;
        }
        return memo[start]=false;
    }
}

解法二：DP

“可以记忆化递归的大多都可以DP解决”（没错，就是我说的）

//如果截止j位置满足条件，那么只要set.contains(s.substring(j,i)),则说明截止i也满足条件
//即转移方程如下
if( dp[j] && set.contains(s.substring(j,i))){dp[i]=true;}

因此可以改写为以下形式

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set=new HashSet<String>(wordDict);
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;									
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                if( dp[j] && set.contains(s.substring(j,i)))
                    dp[i]=true;
            }
        }
        return dp[s.length()];
    }
}

120. Triangle

image-20200505150432163

解法一：直接递归dfs

应该可以，但是超时了

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty()) return 0;
        return getMin(triangle, 0, 0, 0);
    }

    int getMin(vector<vector<int>>& triangle, int level, int idx, int sum) {
        if(level > triangle.size() - 1) return sum;
        if(idx > triangle[level].size() - 1) return INT32_MAX;
        return std::min(getMin(triangle, level + 1, idx + 1, sum), getMin(triangle, level + 1, idx, sum)) + triangle[level][idx];
    }
};

解法二：记忆化递归

class Solution {
public:
    vector<vector<int>> memo;
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty()) return 0;
        memo = vector<vector<int>>(triangle.size(), vector<int>(triangle.size(), -1));
        return getMin(triangle, 0, 0, 0);
    }

    int getMin(vector<vector<int>>& triangle, int level, int idx, int sum) {
        if(level > triangle.size() - 1) return sum;
        if(idx > triangle[level].size() - 1) return INT32_MAX;
        if(memo[level][idx] != -1) return memo[level][idx];
        int min = std::min(getMin(triangle, level + 1, idx + 1, sum), getMin(triangle, level + 1, idx, sum)) + triangle[level][idx];
        return memo[level][idx] = min;
    }
};

解法三：自顶向下DP

转移方程：

if(j == 0) 
	memo[i][j] = memo[i-1][j] + triangle[i][j];
else if(j == triangle[i].size() - 1) 
	memo[i][j] = memo[i-1][j-1] + triangle[i][j];
else 
	memo[i][j] = triangle[i][j] + std::min(memo[i-1][j], memo[i-1][j-1]);

完整代码：

结果是最底层中最小的那个

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty()) return 0;
        vector<vector<int>> memo = vector<vector<int>>(triangle.size(), vector<int>(triangle.size(), -1));
        memo[0][0] = triangle[0][0];
        for(int i = 1; i < triangle.size(); i++){
            for(int j = 0; j < triangle[i].size(); j++){
                if(j == 0) 
                    memo[i][j] = memo[i-1][j] + triangle[i][j];
                else if(j == triangle[i].size() - 1) 
                    memo[i][j] = memo[i-1][j-1] + triangle[i][j];
                else 
                    memo[i][j] = triangle[i][j] + std::min(memo[i-1][j], memo[i-1][j-1]);
            }
        }
        int res = INT32_MAX, len = memo[memo.size() - 1].size();
        for(int i = 0; i < len; i++) res = std::min(res, memo[memo.size() - 1][i]);
        return res;
    }
};

解法四：自底向上DP

下次再写

221. Maximal Square

image-20200506175441330

解法一：bfs

本质就是暴力搜索，因为每遇到一个1都要开始搜索，而且每层的斜对角都会被重复判断

class Solution {
public:
    struct Pos {
        int x, y;
    };
    int maximalSquare(vector<vector<char>>& matrix) {
        int size = 0;
        for(int i = 0; i < matrix.size(); i++) {
            for(int j = 0; j < matrix[0].size(); j++) {
                if(matrix[i][j] == '1')
                    size = std::max(size, bfs(matrix, i, j));
            }
        }
        return size * size;
    }

    int bfs(vector<vector<char>>& matrix, int i, int j) {
        queue<Pos> q;
        q.push({i, j});
        int size = 0;
        while(!q.empty()) {
            int len = q.size();
            for(int idx = 0; idx < len; idx++) {
                Pos curr = q.front(); q.pop();
                i = curr.x, j = curr.y;
                if(i > matrix.size() - 1 || j > matrix[0].size() - 1) 
                    return size;
                if(matrix[i][j] == '0') 
                    return size;
                q.push({i + 1, j});
                q.push({i, j + 1});
                q.push({i + 1, j + 1});
            }
            size++;
        }
        return size;
    }
};

解法二：DP

转移方程：

dp[i][j] = min{ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] } + 1;

完整解法：

class Solution {
    public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return 0;
        vector<vector<int>> dp = vector<vector<int>>(matrix.size(), vector<int>(matrix[0].size()));
        int size = 0;
        for(int i = 0; i < matrix.size(); i++) {
            for(int j = 0; j < matrix[0].size(); j++) {
                if(matrix[i][j] == '1') {
                    if(i == 0 || j == 0)
                        dp[i][j] = 1;
                    else
                        dp[i][j] = std::min(dp[i-1][j], std::min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
                size = std::max(size, dp[i][j]);
            }
        }
        return size * size;
    }
};

523. Continuous Subarray Sum

image-20200514133707446

这题好像根本不是DP，被骗了orz

解法一：暴力法

两重循环枚举所有情况，注意处理0的情况

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(nums.empty()) return false;
        for(int i = 0; i < nums.size(); i++) {
            int sum = nums[i];
            for(int j = i + 1; j < nums.size(); j++) {
                sum += nums[j];
                if(k == 0) {
                    if(sum == 0) return true;
                } 
                else {
                    if(sum % k == 0) return true;
                }
            }
        }
        return false;
    }
};

解法二：前缀和

  • 记录前缀和以及对应的index
  • 检查是否存在某个前缀和与当前前缀和相减 mod k 为0（或k为0时，差也为0）
  • 再检查索引差是否大于一
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(nums.empty()) return false;
        unordered_map<int, int> map;
        map[0] = -1;
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if(k != 0) sum %= k;
            if(map.find(sum) != map.end()) {
                if(i - map[sum] > 1) return true;
            }
            else {
                map[sum] = i;
            }
        }

        return false;
    }
};

1024. Video Stitching

image-20200514160149449

image-20200514160200566

解法一：排序 + 贪心

  • 先排序，每次更新能覆盖的最长片段，如果下一个的起始点超过了当前覆盖的范围，说明无解

  • 在下次起始点不超过本次范围的情况下，寻找一个覆盖范围最广的片段

  • 如果满足 >= T 那么返回结果

  • 排序$O(Nlog(N))$ + 线性遍历$O(N)$ = $O(Nlog(N))$

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        std::sort(clips.begin(), clips.end());
        int curr = 0, res = 0;
        for(int i = 0; i < clips.size(); i++) {
            if(clips[i][0] > curr) return -1;
            int tmp = clips[i][1];
            while(i + 1 < clips.size() && clips[i + 1][0] <= curr)
                tmp = std::max(tmp, clips[++i][1]);
            res++;
            curr = tmp;
            if(curr >= T) return res;
        }
        return -1;
    }
};

1027. Longest Arithmetic Sequence

image-20200514163832672

解法一：暴力法

先枚举所有可能的差，再检查对应差的最大长度，用最大长度更新我们的解

14000+ms，震撼我妈

class Solution {
public:
    int max = 0;
    int longestArithSeqLength(vector<int>& A) {
        if(A.size() < 2) return A.size();
        for(int i = 0; i < A.size(); i++) {
            for(int j = i + 1; j < A.size(); j++) {
                dfs(A, j, A[j] - A[i], 2);
            }
        }
        return max;
    }

    void dfs(vector<int>& nums, int start, int val, int len) {
        max = std::max(len, max);
        for(int i = start + 1; i < nums.size(); i++) {
            if(nums[i] - nums[start] == val) {
                dfs(nums, i, val, len + 1);
            }
        }
    }
};

解法二：记忆化 & DP

  • 记录下到 i 位置为止的所有差值对应等差数列的长度

  • 如果A[i] - A[j] ( j < i ) ，转移方程为

    // dp[j]中存在 A[i] - A[j]
dp[i][A[i] - A[j]] = dp[j][A[i] - A[j]] + 1
// 否则
dp[i][A[i] - A[j]] = 2

  • 不断更新最大值

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        // if(A.size() == 1000) return 5;
        // if(A.size() == 2000) return 6;
        if(A.size() < 2) return A.size();
        vector<unordered_map<int, int>> dp(A.size());
        int res = 2;
        for(int i = 1; i < A.size(); i++) {
            for(int j = 0; j < i; j++) {
                int val = A[i] - A[j];
                if(dp[j].find(val) == dp[j].end())
                    dp[i][val] = 2;
                else    
                    dp[i][val] = dp[j][val] + 1;
                res = std::max(res, dp[i][val]);
            }
        }
        return res;
    }
};

576. Out of Boundary Paths

image-20200514180330408

解法一：DP

看到$10^9$应该知道暴力法是没希望的，大概率是DP计数

代码参考花花酱, 用循环 + 方向数组判断四个方向越界情况值得学习

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
        int mask = 1e9 + 7;
        vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(m, vector<int>(n, 0)));
        vector<int> dirs = {-1, 0, 1, 0, -1};
        for (int s = 1; s <= N; s++) {
            for (int y = 0; y < m; y++) {
                for (int x = 0; x < n; x++) {
                    for (int i = 0; i < 4; i++) {
                        int nx = x + dirs[i];
                        int ny = y + dirs[i + 1];
                        if(nx < 0 || ny < 0 || nx >= n || ny >= m) {
                            dp[s][y][x]++;
                        }
                        else
                            dp[s][y][x] = (dp[s][y][x] + dp[s - 1][ny][nx]) % mask;
                    }
                }
            }
        }

        return dp[N][i][j];
    }
};

712. Minimum ASCII Delete Sum for Two Strings

image-20200923161745469

解法一： DP

本质上是最长公共子序列的变形，可以用DP来解决

  • 对于两者其中之一为空的情况

    dp[i][j] = dp[i + 1][j] + s2[j];
dp[i][j] = dp[i][j + 1] + s1[i];

  • 对于两者相等的情况

    dp[i][j] = dp[i + 1][j + 1];

  • 不相等的情况

    dp[i][j] = min(dp[i + 1][j] + s1[i],
               dp[i][j + 1] + s2[j]);

完整解法

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for(int i = n1 - 1; i > -1; --i)
            dp[i][n2] = dp[i + 1][n2] + s1[i];
        for(int j = n2 - 1; j > -1; --j)
            dp[n1][j] = dp[n1][j + 1] + s2[j];
        for(int i = n1 - 1; i > -1; --i) {
            for(int j = n2 - 1; j > -1; --j) {
                if(s1[i] == s2[j])
                    dp[i][j] = dp[i + 1][j + 1];
                else
                    dp[i][j] = min(dp[i + 1][j] + s1[i], dp[i][j + 1] + s2[j]);
            }
        }
        return dp[0][0];
    }
};
© 2020 Overyam - Powered by Hexo - Theme Chan