前6题为必做题，最后2题为选做题！
写在前面：
题目还是没那么难的，只是有些东西不好理解，可以像老师一样画图帮助理解
AC代码：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int n;
public static int[][]arr,Maxsum;
public static int solve(int i,int j){
if(Maxsum[i][j]>=0)return Maxsum[i][j];
if(i==n)return arr[i][j];
else {
Maxsum[i][j]=Math.max(solve(i+1,j),solve(i+1,j+1))+arr[i][j];
}
return Maxsum[i][j];
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
n=sc.nextInt();
arr=new int[110][110];
Maxsum=new int[110][110];
// Arrays.fill(Maxsum,-1);只适用一维数组
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
arr[i][j]=sc.nextInt();
Maxsum[i][j]=-1;
}
}
System.out.println(solve(1,1));
}
}
}
这里面的dp数组的初始化用了循环，如果是对于一维数组的初始化可以使用Arrays.fill()函数
2、问题 B: 滚球游戏AC代码：
import java.util.Scanner;
public class Main {
public static int n;
public static int[][]arr,Maxsum;
public static void solve(){
for(int j=1;j<=2*n-1;j++){
Maxsum[n][j]=arr[n][j];
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=2*i-1;j++){
int max = Math.max(Maxsum[i + 1][j], Maxsum[i + 1][j + 1]);
max = Math.max(max, Maxsum[i + 1][j+2]);
// System.out.println("**"+max+"**"+Maxsum[i + 1][j+2]);
Maxsum[i][j]=max+arr[i][j];
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int flag=0;
while(sc.hasNext()){
if(flag==0){
n=sc.nextInt();
arr=new int[550][550];
Maxsum=new int[550][550];
flag=1;
}else{
sc.nextLine();
n=sc.nextInt();
arr=new int[550][550];
Maxsum=new int[550][550];
}
// Arrays.fill(Maxsum,-1);只适用一维数组
for(int i=1;i<=n;i++){
for(int j=1;j<=2*i-1;j++){
arr[i][j]=sc.nextInt();
Maxsum[i][j]=-1;
}
}
solve();
System.out.println(Maxsum[1][1]);
}
}
}
这里需要注意的是数组的大小，开大一点，110*110的是不够的，会有运行错误
3、最长公共子序列问题(LCS)之备忘录法AC代码：
import java.util.Scanner;
public class Main {
public static int[][]c=new int[550][550];;
public static int solve(char[]str1,char[]str2,int i,int j){
if(c[i+1][j+1]==-1){
if(i==0||j==0)c[i][j]=0;
else if(str1[i-1]==str2[j-1]){
c[i][j]=solve(str1,str2,i-1,j-1)+1;
}else{
c[i][j]=Math.max(solve(str1,str2,i,j-1),solve(str1,str2,i-1,j));
}
}
return c[i][j];
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
char[]str1=sc.nextLine().toCharArray();
char[]str2=sc.nextLine().toCharArray();
int n=Math.min(str1.length,str2.length);
int m=Math.max(str1.length,str2.length);
for(int i=0;i<550;i++){
for(int j=0;j<550;j++){
c[i][j]=-1;
}
}
System.out.println(solve(str1,str2,str1.length,str2.length));
}
}
4、问题 D: 最长公共子序列问题(LCS)之动态规划法
AC代码：
import java.util.Scanner;
public class Main {
public static int[][]c=new int[550][550];//初始值就是0
public static void solve(char[]str1,char[]str2,int i,int j){
for(int k=1;k<=i;k++){
for(int m=1;m<=j;m++){
if(str1[k-1]==str2[m-1])c[k][m]=c[k-1][m-1]+1;
else if(c[k][m-1]>=c[k-1][m])c[k][m]=c[k][m-1];
else c[k][m]=c[k-1][m];
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
char[]str1=sc.nextLine().toCharArray();
char[]str2=sc.nextLine().toCharArray();
solve(str1,str2,str1.length,str2.length);
System.out.println(c[str1.length][str2.length]);
}
}
5、问题 E: 最长公共子序列问题(LCS)-构造LCS
AC代码：
import java.util.Scanner;
public class Main {
public static int[][]c=new int[550][550];//初始值就是0
public static int[][]b=new int[550][550];
public static void solve(char[]str1,char[]str2,int i,int j){
for(int k=1;k<=i;k++){
for(int m=1;m<=j;m++){
if(str1[k-1]==str2[m-1]){
c[k][m]=c[k-1][m-1]+1;
b[k][m]=1;
}
else if(c[k][m-1]>=c[k-1][m]){
c[k][m]=c[k][m-1];
b[k][m]=3;
}
else {
c[k][m]=c[k-1][m];
b[k][m]=2;
}
}
}
}
public static void solve2(int i,int j,char[]x,int[][]b){
if(i==0||j==0)return;
if(b[i][j]==1){
solve2(i-1,j-1,x,b);
System.out.print(x[i-1]);
}else if(b[i][j]==2){
solve2(i-1,j,x,b);
}else if(b[i][j]==3){
solve2(i,j-1,x,b);
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
char[]str1=sc.nextLine().toCharArray();
char[]str2=sc.nextLine().toCharArray();
solve(str1,str2,str1.length,str2.length);
solve2(str1.length,str2.length,str1,b);
}
}
6、问题 F: 牛牛的字符串
AC代码：
import java.util.Scanner;
public class Main {
public static int solve(char[]str1,char[]str2){
if (str1 == null || str2 == null) {
return 0;
}
int result = 0;
int sLength = str1.length;
int tLength =str2.length;
int[][] dp = new int[sLength][tLength];
for (int i = 0; i < sLength; i++) {
for (int k = 0; k < tLength; k++) {
if (str1[i]==str2[k]) {
if (i == 0 || k == 0) {
dp[i][k] = 1;
} else {
dp[i][k] = dp[i - 1][k - 1] + 1;
}
result = Math.max(dp[i][k], result);
} else {
dp[i][k] = 0;
}
}
}
return result;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
char[]str1=sc.nextLine().toCharArray();
char[]str2=sc.nextLine().toCharArray();
System.out.println(solve(str1,str2));
}
}
学到动态规划突然发现自己好差劲啊，脑子不聪明只好多花时间了
