动态规划算法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();

}

}