动态规划算法java代码 动态规划算法java代码怎么写
·代表任意一个字符，*代表任意一串字符，判断两个字符串是否匹配？
Java代码：
成都创新互联-专业网站定制、快速模板网站建设、高性价比高州网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式高州网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖高州地区。费用合理售后完善，10年实体公司更值得信赖。
public static void main(String[] args) {
System.out.println(isMatch("asdfgvbbnchb", "as*bnc.b"));
}
/**
* 动态规划法判断普通字符串是否与通配符字符串匹配。
*
* pre
* 算法思路：
* 设s为普通字符串，p为通配符字符串，字符串中字符编号以0起始。
* 申请布尔型数组 dp[s.length+1][p.length+1]。
* 1. dp[0][0]表示s为空串、p为空串时是否匹配，显然为true，dp[0][0]=true。
* 2. dp[0][j+1]，0=jp.length，表示s为空串时，s与p[0..j]是否匹配，
* 当dp[0][j]=true且p[j]='*'时，dp[0][j+1]=true。
* 如果dp[0][j]=false，即p[0..j-1]已经不能与空串匹配了，显然加上p[j]
* 也不能匹配。
* 如果p[j]!='*'，则p[j]必须与一个字符匹配，而s为空串，显然不能匹配。
* 3. dp[i+1][j+1]表示s[0..i]与p[0..j]是否匹配。
* 3.1 如果p[j]='*'，那么可以有两种匹配方式：
* 方式1. p[j]与s[i]匹配，s[i]被匹配掉后，还需判断s[0..i-1]是否与
* p[0..j]匹配，故dp[i+1][j+1]=dp[i][j+1]。
* 方式2. p[j]不与s[i]匹配，这时还需判断s[0..i]是否与p[0..j-1]匹配，
* 故dp[i+1][j+1]=dp[i+1][j]。
* 综合两种情况，dp[i+1][j+1]=dp[i][j+1]||dp[i+1][j]。
* 3.2 如果p[j]='.'，则p[j]必须和s[i]匹配，还需判断s[0..i-1]是否与
* p[0..j-1]匹配，故dp[i+1][j+1]=dp[i][j]。
* 3.3 如果p[j]为其他字符并且与s[i]相同，则p[j]必须和s[i]匹配，还需判断
* s[0..i-1]是否与p[0..j-1]匹配，故dp[i+1][j+1]=dp[i][j]。
* 这种情况可以与情况3.2合并。
* 最终 dp[s.length][p.length] 即表示s与p是否匹配。
* /pre
*
* @param s
* 普通字符串。
* @param p
* 通配符字符串。
* @return 如果普通字符串与通配符字符串匹配则返回true，否则返回false。
*/
public static boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int j = 0; j p.length(); j++) {
if (dp[0][j] p.charAt(j) == '*') {
dp[0][j + 1] = true;
}
}
for (int i = 0; i s.length(); i++) {
for (int j = 0; j p.length(); j++) {
if (p.charAt(j) == '*') {
dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j];
} else if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {
dp[i + 1][j + 1] = dp[i][j];
}
}
}
return dp[s.length()][p.length()];
}
java动态规划算法求给定的值
public class Test { /*创建类*/public static void main(String[] args) {System.out.println(dg(100));}static int dg(int i) { /*定义变量 */int sum;if (i == 1) /*假设条件*/return 1;elsesum = i + dg(i - 1); /*1~100的和的表达式*/retur...
~~求解~~用动态规划算法求两数组各元素间差的最小值，JAVA代码或方法思路
import java.util.Arrays;
public class Test {
public static void getCha(int [] a,int []b){
int min =Integer.MAX_VALUE;
int sss=0;
int kkk = 0;
int c = 0;
int d = 0;
for (int i = 0; i a.length; i++) {
for (int j = 0; j b.length; j++) {
int temp = Math.abs(a[i]-b[j]);
if(tempmin){
min = temp;
sss = a[i];
kkk = b[j];
c=i;
d=j;
}
}
}
System.out.println("最大差距："+min+"数组A["+c+"]"+sss+"数组B["+d+"]"+kkk);
}
public static void main(String[] args) {
int []a = new int[8];
int []b = new int[12];
for (int i = 0; i a.length; i++) {
a[i] = (int)( Math.random()*100);
}
System.out.println(Arrays.toString(a));;
for (int i = 0; i b.length; i++) {
b[i] = (int) (Math.random()*100);
}
System.out.println(Arrays.toString(b));
getCha(a,b);
}
}
java动态规划 计算数n由k个数相加而成的情况数
public class MyClass {
public static void main(String[] args) {
System.out.println(" result count:" + method(6, 3));
}
public static int method(int n, int k) {
ListListInteger list = new ArrayList();
for (int i = 0; i k; i++) {
if (i == 0) {
for (int j = 1; j n; j++) {
ListInteger li = new ArrayList();
li.add(j);
list.add(li);
}
continue;
}
ListListInteger listNew = new ArrayList();
for (ListInteger integers : list) {
for (int j = integers.get(integers.size() - 1); j n; j++) {
ListInteger li = new ArrayList();
li.addAll(integers);
li.add(j);
listNew.add(li);
if (i + 1 == k) {
int res = 0;
for (Integer integer : li) {
res += integer;
}
if (res != n) {
listNew.remove(li);
}
}
}
}
list.clear();
list.addAll(listNew);
}
for (ListInteger integers : list) {
for (Integer integer : integers) {
System.out.print(integer + "\t");
}
System.out.println();
}
return list.size();
}
}
本文标题：动态规划算法java代码 动态规划算法java代码怎么写
本文地址：http://azwzsj.com/article/dojogje.html
