[数据结构与算法]力扣剑指offer2第33天动态规划

97）子序列的数目

class Solution{
public:
    int numDistinct(string s, string t){
        int m=s.size(), n=t.size();
        if(m<n) return 0;
        vector<vector<unsigned long long>> dp(m+1, vector<unsigned long long>(n+1, 0));
        for(long i=0; i<=m; i++) dp[i][n]=1;
        for(long i=m-1; i>=0; i--){
            char ch1=s[i];
            for(long j=n-1; j>=0; j--){
                char ch2=t[j];
                if(ch1==ch2){
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j];
                }else{
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }
};
        

98)路径的数目

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

99)最小路径之和

class Solution{
public:
    int minPathSum(vector<vector<int>>& grid){
        int m=grid.size(), n=grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = grid[0][0];
        for(int i=1; i<m; i++) dp[i][0]= dp[i-1][0] + grid[i][0];
        for(int j=1; j<n; j++) dp[0][j]= dp[0][j-1] + grid[0][j];
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};