Question

java 动态规划矩阵多少种走法

Answer 1

import java.util.Scanner;
public class zhidao3
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
int out[] = new int[T];
scanner.nextLine();
for(int t=0;t<T;t++)
{
String a = scanner.nextLine();
char[] ch=a.toCharArray();
int f[][]= new int[ch.length+1][2];
if (ch[0]<='Z'&&ch[0]>='A')
{
f[0][1]=2;
f[0][0]=2;
}
if (ch[0]<='z'&&ch[0]>='a')
{
f[0][1]=1;
f[0][0]=1;
}
for(int i=1 ;i<=ch.length;i++)
{
if (ch[i-1]<='Z'&&ch[i-1]>='A')
{
f[i][0] = f[i-1][1] + 2;
f[i][1] = f[i-1][1] + 1;
}
if(ch[i-1]<='z'&&ch[i-1]>='a')
{
f[i][0] = f[i-1][0] + 1;
f[i][1] = f[i-1][0] + 2;
}
}
out[t] = Math.min(f[ch.length-1][0],f[ch.length-1][1]);

}
for(int t=0;t<T;t++){
System.out.println(out[t]);//最后统一输出
}
scanner.close();
}
}