本文主要是介绍uva10069（DP+大数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：找出B串在A串出现的次数（B在A中可以是不连续的）
解答：设母串的长度是j，子串的长度数i，在假设dp[i][j]:是在长度是j的母串中出现长度是i的子串的个数，如果A[j]！=B[i]，dp[i][j]=dp[i][j-1]
如果A[j]==B[i]; dp[i][j]=dp[i-][j-1]+dp[i][j-1];
A[j]==B[i]的状态转移，可以这样理解假设此时A串，B串如下（X,#代表其他的字符）
A: XXXXXXG
B: ###G
此时A[7]==B[4]，所以你会判断
1：### 在 XXXXXX 中出现的次数
2：###G 在 XXXXXX 中出现的次数
答案是1与2的和
对于大数直接用JAVA好了
import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String args[]){int n;Scanner cin=new Scanner(System.in);while(cin.hasNext()){BigInteger dp[][]=new BigInteger[110][10010];n=cin.nextInt();String a,b;while(n-->0){a=cin.next();b=cin.next();for(int i=0;i<dp.length;i++){for(int j=0;j<dp[i].length;j++){dp[i][j]=BigInteger.ZERO;}}for(int i=0;i<=a.length();i++){dp[0][i]=BigInteger.ONE;}for(int i=1;i<=b.length();i++){for(int j=i;j<=a.length();j++){if(b.charAt(i-1)==a.charAt(j-1)){dp[i][j]=dp[i][j-1].add(dp[i-1][j-1]);}else {dp[i][j]=dp[i][j-1];}}}System.out.println(dp[b.length()][a.length()]);}}}
}
这篇关于uva10069（DP+大数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
