LeetCode动态规划合集

1.LeetCode474一和零

题目:

给你一个二进制字符串数组 strs 和两个整数 mn

请你找出并返回 strs 的最大子集的大小,该子集中 最多m0n1

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y子集

示例1:

输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

示例2:

输入:strs = ["10", "0", "1"], m = 1, n = 1
输出:2
解释:最大的子集是 {"0", "1"} ,所以答案是 2 。

思路:

01背包,遍历每一个字符串,统计字符串中0和1的个数,再进行01背包

dp[i][j]表示有i个0和j个1的最大字符串个数

class Solution {
    
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp=new int[m+1][n+1];
        for(String s:strs){
            int zs=0,os=0;
            for(int i=0;i<s.length();i++){
                if(s.charAt(i)=='0'){
                    zs++;
                }else{
                    os++;
                }
            }
            for(int i=m;i>=zs;i--)
                for(int j=n;j>=os;j--){
                    dp[i][j]=Math.max(dp[i][j],dp[i-zs][j-os]+1);
                }
        }
        return dp[m][n];
    }
}

2.LeetCode837新21点

题目:

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏,描述如下:

爱丽丝以 0 分开始,并在她的得分少于 K 分时抽取数字。 抽取时,她从 [1, W] 的范围中随机获得一个整数作为分数进行累计,其中 W 是整数。 每次抽取都是独立的,其结果具有相同的概率。

当爱丽丝获得不少于 K 分时,她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少?

示例1:

输入:N = 10, K = 1, W = 10
输出:1.00000
说明:爱丽丝得到一张卡,然后停止。

示例2:

输入:N = 6, K = 1, W = 10
输出:0.60000
说明:爱丽丝得到一张卡,然后停止。
在 W = 10 的 6 种可能下,她的得分不超过 N = 6 分。

class Solution {
    public double new21Game(int N, int k, int W) {
        //如果当点数为K-1时,只有能抽取最后一张牌的机会,只要保证最后一张牌的最大值也就是w 加上K-1不超过N,则概率为1
        if(N>=W+k-1)
            return 1.0;
        double[] dp=new double[k+W+1];
        //当抽的点数>=k时游戏结束,现在手上的点数在k~N则概率为1
        for(int i=k;i<=N;i++)
            dp[i]=1.0;
        
        //最后一次抽卡保证能赢得游戏的最大点数
        double s=N-k+1;
    //这里我们知道手上点数为 17 时赢得游戏的概率为 100%,所以 K ~ N 区间的赢得游戏的概率为 100%,超过 N 时赢得游戏概率为 0,那么手上点数为 16 时,赢得游戏的概率就是 手上点数为 17      ~ 17 + 10 - 1 的赢得游戏的概率和除以 W

        for(int i=k-1;i>=0;i--){
            dp[i]=s/W;//手里还剩i和点数时赢得游戏的概率
            s+=-dp[i+W]+dp[i];//
        }

        return dp[0];
    }
}

3.LeetCode1143.最长公共子序列

题目:

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例1:

输入:text1 = "abcde", text2 = "ace" 
输出:3  
解释:最长公共子序列是 "ace",它的长度为 3。

示例2:

输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc",它的长度为 3。
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
            int n=text1.length(),m=text2.length();
            int maxn=Math.max(n,m);
            int[][] dp=new int[n+1][m+1];//dp[i][j]表示s1字符串0~i和s2字符串0~j的最长公共子序列
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++){
                    if(text1.charAt(i-1)==text2.charAt(j-1))
                        dp[i][j]=dp[i-1][j-1]+1;
                    else
                        dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            return dp[n][m];
    }
}

4.LeetCode1641.统计字典序元音字符串的数目

题目:

给你一个整数 n,请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

字符串 s 按 字典序排列 需要满足:对于所有有效的 i,s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

示例:

输入:n = 1
输出:5
解释:仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例:

输入:n = 2
输出:15
解释:仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意,"ea" 不是符合题意的字符串,因为 'e' 在字母表中的位置比 'a' 靠后

class Solution {
    public int countVowelStrings(int n) {
        //dp[i][j]表示长度为i且以第j个字母结尾的字符串
        int[][] dp=new int[n+1][5];
        for(int i=0;i<5;i++){
            dp[1][i]=1;
        }
        for(int i=2;i<=n;i++){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][0]+dp[i-1][1];
            dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
            dp[i][3]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3];
            dp[i][4]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4];
        }
        return dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3]+dp[n][4];
    }
}

5.剑指offer 14-| 剪绳子

题目:

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]k[1]...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
class Solution {
    public int cuttingRope(int n) {
        //dp[i]表示长度为i的绳子能够分割后的最大乘积
        int[] dp=new int [n+1];
        dp[1]=1;
        /*
            对于dp[i]分割成i和i-j有以下四种情况
            1.i和i-j不再细分,结果为i*(i-j)
            2.i细分,i-j不再细分,结果为dp[i]*(i-j)
            3.i不再细分,i-j继续细分,结果为i*dp[i-j]
            4.i和i-j都细分,结果为dp[i]*dp[i-j];

        */
        for(int i=2;i<=n;i++)
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],dp[j]*dp[i-j]);
                dp[i]=Math.max(dp[i],j*(i-j));
                dp[i]=Math.max(dp[i],dp[j]*(i-j));
                dp[i]=Math.max(dp[i],j*dp[i-j]);
            } 
        return dp[n];
    }
}

6.剑指offer 14-|| 剪绳子

题目:

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]k[1]...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

7.LeetCode1314.矩阵区域和

题目:

给你一个 m * n 的矩阵 mat 和一个整数 K ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:

  • i - K <= r <= i + K, j - K <= c <= j + K
  • (r, c) 在矩阵内

示例1:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
输出:[[12,21,16],[27,45,33],[24,39,28]]

示例2:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
输出:[[45,45,45],[45,45,45],[45,45,45]]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, K <= 100
  • 1 <= mat[i][j] <= 100
class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m=mat.length,n=mat[0].length;
        int[][] dp=new int[m+1][n+1];
        int[][] ans=new int[m][n];

        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]-dp[i-1][j-1]+mat[i-1][j-1];
            } 
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                int li=Math.max(i-k,0);
                int lj=Math.max(j-k,0);
                int ri=Math.min(i+k,m-1);
                int rj=Math.min(j+k,n-1);

                ans[i][j]=dp[ri+1][rj+1]-dp[li][rj+1]-dp[ri+1][lj]+dp[li][lj];
            }

            return ans;
    }
}

8.LeetCode279.完全平方数

题目:

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例:

输入:n = 12
输出:3 
解释:12 = 4 + 4 + 4

完全背包

class Solution {
    public int numSquares(int n) {
            int[] dp=new int[n+1];
            for(int i=1;i<=n;i++){
                dp[i]=i;//最坏的情况就是全是1相加
                for(int j=1;j*j<=i;j++)
                    dp[i]=Math.min(dp[i],dp[i-j*j]+1);
            }
            return dp[n];
    }
}

9.剑指offer63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

示例1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

class Solution {
    public int maxProfit(int[] prices) {
            int n=prices.length;
            int minx=99999999;
            int ans=0;
            for(int i=0;i<n;i++){
                minx=Math.min(minx,prices[i]);
                ans=Math.max(ans,prices[i]-minx);
            }
            return ans;
    }
}

10.LeetCode122.买卖股票的最佳时机||

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

提示:

  • 1 <= prices.length <= 3 * 10 ^ 4

  • 0 <= prices[i] <= 10 ^ 4

DP

class Solution {
    public int maxProfit(int[] prices) {
            int n=prices.length;
            int[][] dp=new int[n+1][2];
            //dp[i][0]表示第i天手里没有股票的最大利润,dp[i][1]表示第i天手里有股票的最大利润
            dp[0][1]=-prices[0];
            for(int i=1;i<n;i++){
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
                dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            }
            return dp[n-1][0];
    }
}

贪心

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

11.LeetCode123.买卖股票的最佳时机|||

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例:

输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得1利润 = 4-1 = 3 。

class Solution {
public:
    int f[100005][3][2];//表示到第i天进行了k笔交易 01表示当前手中是否有股票
    int maxProfit(vector<int>& prices) {
        int ans=-1;
        int n=prices.size();
        memset(f,-0x3f,sizeof f);
        for(int i=0;i<=n;i++) f[i][0][0]=0;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=2;j++){
 //当前有股由上次没有和上次有转移过来。由于上次有而这次无,完成卖出操作,所以第二维j不是j-1。	
                f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+prices[i-1]);
 ////同上,由于新增买入操作,所以是j-1层转移过来。
                f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]);
            }
        for(int i=0;i<=2;i++){
            ans=max(ans,f[n][i][0]);
        }
        return ans;
    }
};

12.LeetCode188..买卖股票的最佳时机IV

给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

class Solution {
public:
    int f[10000][105][2];
    int w[10000];
    int maxProfit(int k, vector<int>& prices) {
     int n=prices.size();
	memset(f,-0x3f,sizeof f);//初始化为负无穷,状态转移时取max,所以到达不了负无穷的状态,输出结果时需要遍历。
	for(int i=0;i<=n;i++) f[i][0][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++){
			f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+prices[i-1]);//当前有股由上次没有和上次有转移过来。由于上次有而这次无,完成卖出操作,所以第二维j不是j-1。
			f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]);//同上,由于新增买入操作,所以是j-1层转移过来。
		}
	int res=0;
	for(int i=0;i<=k;i++) res=max(res,f[n][i][0]);
         return res;
    }       
};

13.LeetCode338.比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

示例1;

输入: 2
输出: [0,1,1]

示例2:

输入: 5
输出: [0,1,1,2,1,2]
class Solution {
    public int[] countBits(int num) {
            int[] ans=new int[num+1];
            for(int i=0;i<=num/2;i++){
                ans[2*i]=ans[i];//一个数的二倍和他1的个数相等,2i+1比他的个数多1
                if(i*2+1<=num)
                    ans[i*2+1]=ans[i]+1;
            }
            return ans;
    }
}

14.蓝桥杯2018决赛 激光样式

x星球的盛大节日为增加气氛,用30台机光器一字排开,向太空中打出光柱。
安装调试的时候才发现,不知什么原因,相邻的两台激光器不能同时打开!
国王很想知道,在目前这种bug存在的情况下,一共能打出多少种激光效果?
显然,如果只有3台机器,一共可以成5种样式,即:
全都关上(sorry, 此时无声胜有声,这也算一种)
开一台,共3种
开两台,只1种
30台就不好算了,国王只好请你帮忙了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


int dp[500][3];//dp[i][1]表示第一共有i栈但第i灯不亮的情况种数 
int main()
{	
	dp[1][0]=1;
	dp[1][1]=1;
	
	for(int i=2;i<35;i++){
		dp[i][0]=dp[i-1][1]+dp[i-1][0];
		dp[i][1]=dp[i-1][0];
	}
	cout<<dp[30][0]+dp[30][1];
	
	return 0;
} 

15.LeetCode.354俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

说明:
不允许旋转信封

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

先根据左端点排序,在求右端点的最长上升子序列

:当左端点一样时不能根据右端点排序,例如[4.6],[4.9],但不能装进去

  bool cmp(vector<int> a,vector<int> b){
        if(a[0]==b[0])
            return a[1]>b[1];
        return a[0]<b[0];
    }
class Solution {
public:
    int dp[100000];
    int maxEnvelopes(vector<vector<int>>& envelopes) {
            int n=envelopes.size();
            sort(envelopes.begin(),envelopes.end(),cmp);
            for(int i=0;i<n;i++)
                dp[i]=1;
            for(int i=0;i<n;i++)
                for(int j=0;j<i;j++){
                    if(envelopes[i][1]>envelopes[j][1])
                        dp[i]=max(dp[i],dp[j]+1);
                }

            int ans=0;
            for(int i=0;i<n;i++){
                ans=max(ans,dp[i]);
            }
            return ans;
            
    }
};

16.LeetCode 486.预测赢家

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数,随后玩家 2 继续从剩余数组任意一端拿取分数,然后玩家 1 拿,…… 。每次一个玩家只能拿取一个分数,分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组,预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例1:

输入:[1, 5, 2]
输出:False
解释:一开始,玩家1可以从1和2中进行选择。
如果他选择 2(或者 1 ),那么玩家 2 可以从 1(或者 2 )和 5 中进行选择。如果玩家 2 选择了 5 ,那么玩家 1 则只剩下 1(或者 2 )可选。
所以,玩家 1 的最终分数为 1 + 2 = 3,而玩家 2 为 5 。
因此,玩家 1 永远不会成为赢家,返回 False 。

二维

class Solution {
    public boolean PredictTheWinner(int[] nums) {
            int n=nums.length;
            int[][] dp=new int[n][n];//dp[i][j]代表当前玩家在i~j范围所得的最大分数
            for(int i=0;i<n;i++)//dp[i][i]为nums[i];
                dp[i][i]=nums[i];
            for(int i=n-2;i>=0;i--)
                for(int j=i+1;j<n;j++){
                    dp[i][j]=Math.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);//如果取左边就是nums[i]减去另一个玩家在i+1~j范围所获得的最大值,也就是dp[i+1][j];
                }
            return dp[0][n-1]>=0;
    }
}

一维优化

17.LeetCode131.分割回文子串

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例1:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]
class Solution {
public:
    vector<vector<int>> f;
    vector<string> ret;
    vector<vector<string>> ans;
    void dfs(string s,int pos){
            if(pos==s.size()){
                ans.push_back(ret);
                return;
            }
            for(int i=pos;i<s.size();i++){
                if(f[pos][i]){
                    ret.push_back(s.substr(pos,i-pos+1));
                    dfs(s,i+1);
                    ret.pop_back();
                }       
         }
    }
    vector<vector<string>> partition(string s) {
            int n=s.size();
            f.assign(n, vector<int>(n, true));
            for(int i=n-1;i>=0;i--)//dp预处理判断i-j是否是回文子串
                for(int j=i+1;j<n;j++){
                    f[i][j]=f[i+1][j-1]&&(s[i]==s[j]);
                }
            dfs(s,0);//dfs枚举子集
            return ans;
    }
};

18.LeetCode.132分割回文串||

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。

返回符合要求的 最少分割次数

示例1:

输入:s = "aab"
输出:1
解释:只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
class Solution {
public:
    int minCut(string s) {
            int n=s.size();
            vector<vector<bool>> is(n,vector<bool>(n,true));
            //dp预处理,判断该子串是否为回文子串
            for(int i=n-1;i>=0;i--)
                for(int j=i+1;j<n;j++)
                    is[i][j]=(s[i]==s[j])&&is[i+1][j-1];

            vector<int> ans(n,INT_MAX);
            for(int i=0;i<n;i++){
                    if(is[0][i])
                         ans[i]=0;//如果0-i的子串为回文串,则需要切割的次数为0
                else{
                    for(int j=0;j<i;j++){
                        if(is[j+1][i]){//如果j+1到i的子串为回文串,则分割次数为0-j的分割次数+
                            ans[i]=min(ans[i],ans[j]+1);
                        }
                    }
                }
            }
            return ans[n-1];
    }
};

19.LeetCode115.不同的子序列

给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)

题目数据保证答案符合 32 位带符号整数范围。

  • 示例 1:

输入:s = "rabbbit", t = "rabbit"
输出:3
解释:
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
(上箭头符号 表示选取的字母)
rabbbit

rabbbit

rabbbit
^^^

  • 示例 2:

输入:s = "babgbag", t = "bag"
输出:5
解释:
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
(上箭头符号 ^ 表示选取的字母)

babgbag

babgbag

babgbag

babgbag

babgbag
^

提示:

  • 0 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成
class Solution {
public:
    int numDistinct(string s, string t) {
            int n=s.size(),m=t.size();
            if(m>n)
                return 0;
            vector<vector<long long>> dp(n+1,vector<long long>(m+1));
            for(int i=0;i<=n;i++)
                dp[i][m]=1;//t为空字符串,任何字符串匹配都为1
            for(int i=n-1;i>=0;i--)
                for(int j=m-1;j>=0;j--){
                    if(s[i]==t[j])
                        dp[i][j]=dp[i+1][j+1]+dp[i+1][j];//如果两个字符相等,可以选择匹配或者不匹配
                    else
                        dp[i][j]=dp[i+1][j];//不相等就不能匹配
                }
            return dp[0][0];
    }
};

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×