B题我用动态规划做的,真不知道哪里有问题,有没有大佬帮忙看看

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), m = sc.nextInt();
		String[][] arr = new String[n][m];
		sc.nextLine();
		for (int i = 0; i < n; i++) {
			String s = sc.nextLine();
			for(int j = 0;j<m;j++) {
				arr[i][j] = s.charAt(j)+"";
			}
		}
		int[][] dp = new int[n][m];
		//dp[0][0] = arr[0][0].charAt(0);
		for(int i = 0;i<n;i++) {
			for(int j = 0;j<m;j++) {
				dp[i][j] = arr[i][j].charAt(0);
			}
		}
		for(int i = 1;i<n;i++) {
			dp[i][0] = dp[i-1][0] + arr[i][0].charAt(0); 
			arr[i][0] = arr[i-1][0] + arr[i][0];
		}
		for(int i = 1;i<m;i++) {
			dp[0][i] = dp[0][i-1] + arr[0][i].charAt(0); 
			arr[0][i] = arr[0][i-1] + arr[0][i];
		}
		
		for(int i = 1;i<n;i++) {
			for(int j =1;j<m;j++) {
				if(dp[i-1][j]<dp[i][j-1]) {
					arr[i][j] = arr[i-1][j] + arr[i][j];
				}else {
					arr[i][j] = arr[i][j-1] + arr[i][j];
				}
				dp[i][j] += Math.min(dp[i-1][j], dp[i][j-1]);
				
			}
		}
		System.out.println(arr[n-1][m-1]);
	}
}

全部评论

相关推荐

10-07 20:48
门头沟学院 Java
听说改名就会有offer:可能是实习上着班想到后面还要回学校给导师做牛马,看着身边都是21-25的年纪,突然emo了了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务