动态规划解决字符串个数

矫情吗；* 2022-05-19 01:55 126阅读 0赞

![这里写图片描述][70]

public class Solution {
     //动态规划法
     //array(i , j ) 表示T[0,j] 在S[0，i] 中的匹配个数
    //如果不使用S[i] , 那么f(i , j) = f(i-1 , j)
    //如果使用了S[i] , 那么一定有 S[i] == T[j] , f( i , j ) = f(i -1 , j -1 )
    //所以当S[i]==T[j]时，有array( i , j ) = array( i -1 , j ) +　array(i - 1 , j - 1);
    //当S[i]!=T[j]时，有 array( i , j ) = array( i -1 , j );
    //在使用中不难发现该dp二维数组可以降维，注意改变数组元素值时由后往前
        public int numDistinct(String S, String T) {
            int len=T.length();
            int[]arr=new int[len+1];
            arr[0]=1;
            for (int i=1;i<S.length()+1;i++) {
                for(int j=Math.min(i,len);j>0;j--){
    
                    if(S.charAt(i-1)==T.charAt(j-1)){
                       arr[j]=arr[j]+arr[j-1];
                    }
                }
    
            }
    
            return arr[len]; 
        }
    
        public static void main(String[]args){
            //System.out.println("Hello World!");
            String s="rabbbit";
            String t="rabbit";
            Solution so=new Solution();
            System.out.println(so.numDistinct(s,t));
    
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220519/ab2cd902029d4732845b9d9f19662ddc.png
[70 1]: /images/20220519/62e6d35e9ec546b29d3a2b12a602495b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 97交错字符串(动态规划)

> 微信搜一搜：`bigsai` > [大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1] > 关注回复进群即可加入力扣打卡群，欢迎划水。近期打卡：

比眉伴天荒/ 2023年01月01日 14:48/ 0 赞/ 103 阅读

相关双序列型动态规划——交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分

梦里梦外;/ 2022年10月27日 12:07/ 0 赞/ 137 阅读

相关字符串上的动态规划算法应用

经常遇到字符串上的相关问题，有涉及到一个字符串和两个字符串的，它们解题方式类似，都是采用动态规划算法来解决，这里做一个整理归纳。 1.求整数序列中的最长增长子序列，和字符串问

「爱情、让人受尽委屈。」/ 2022年09月30日 07:29/ 0 赞/ 64 阅读

相关 leetcode动态规划(字符串+递增子序列)

1. 最长递增子序列给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

小鱼儿/ 2022年09月10日 05:17/ 0 赞/ 101 阅读

相关动态规划：计算字符串相似度

《编程之美》第223页。题目描述许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，

古城微笑少年丶/ 2022年08月08日 05:23/ 0 赞/ 168 阅读

相关 poj 3280 字符串上的动态规划

添加或者删除一些字母，使这个字符串变成回文串。每个字母添加和删除的代价不一样。问最小代价。看别人的思路，在字符串两端删除和添加字母是等价的，因此只需要保留删除和添加中最小的

谁践踏了优雅/ 2022年08月03日 05:14/ 0 赞/ 111 阅读

相关动态规划---计算等差数列的个数

1、题目： A sequence of number is called arithmetic if it consists of at least three elemen

谁践踏了优雅/ 2022年05月23日 08:00/ 0 赞/ 113 阅读

相关动态规划解决字符串个数

![这里写图片描述][70] public class Solution { //动态规划法 //array(i , j ) 表示T[0,j] 在

矫情吗；*/ 2022年05月19日 01:55/ 0 赞/ 127 阅读

相关字符串上的简单动态规划

因为数据结构快学串了，以前又做过一些字符串dp的题，今天突然就想把它们写在一起吧。直接开始问题1：给两个字符串，求最长公共子串问题2：给两个字符串，求最长公共子序列

我就是我/ 2022年05月12日 01:48/ 0 赞/ 135 阅读

相关动态规划：交错字符串

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3

我会带着你远行/ 2022年04月10日 13:41/ 0 赞/ 123 阅读