leetcode动态规划hard

补一下leetcode的动态规划专题

leetcode 10: https://leetcode-cn.com/problems/regular-expression-matching/

class Solution {
public:
    bool isMatch(string s, string p) {
        int ls = s.length(), lp = p.length();
        vector<vector<int>> dp(ls+1, vector<int>(lp+1, 0)); 
        dp[0][0] = 1;

        // i=0为匹配开头*匹配0次的情况
        for (int i = 0; i <= ls; i++) {
            for (int j = 1; j <= lp; j++) {
               if (p[j-1] == '*') {
                   // 匹配0次
                   dp[i][j] = dp[i][j-2];
                   // 当s[i] == p[j-1] 时，p[j-1]匹配无数次
                   if (i > 0 && (s[i-1] == p[j-2] || p[j-2] == '.')) {
                       dp[i][j] = (dp[i][j] || dp[i-1][j]);
                   }
               }
               else {
                   // 字母匹配
                   if (i > 0 && (s[i-1] == p[j-1] || p[j-1] == '.')) {
                        dp[i][j] = dp[i-1][j-1];
                   }
               }
            }
        }

        // for (int i = 0; i <= ls; i++) {
        //     for (int j = 0; j <= lp; j++) {
        //         printf("dp[%d][%d]: %d\n", i, j, dp[i][j]);
        //     }
        // }

        return dp[ls][lp];
    }
};