2021-08-21 17:23 哈尔滨工业大学(威海) C++
关注
#网易笔试#
最后一题那个二维数组的，有大佬用动态规划做出来的吗😿
最后一题那个二维数组的，有大佬用动态规划做出来的吗😿
全部评论
X_T
浙江工业大学 Java
贴一下屎山 XD><
package NetEasy;
import java.util.Scanner;
public class test4 {
public static void main(String[] args) {
// [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]
int[][] mase = new int[][]{{1,1,1,1,0},{0,1,0,1,0},{1,1,2,1,1},{0,2,0,0,1}};
int m = mase.length;
int n = mase[0].length;
int[][] dp = new int[m][n];
dp[0][0] = 0;
// boolean[][] visit = new boolean[m][n];
for(int i = 1; i<n; i++){
if(mase[0][i] != 2 ){
if(mase[0][i] == 1){
dp[0][i] = dp[0][i - 1] + 1;
}
else{
dp[0][i] = dp[0][i - 1] + 2;
}
}
else{
dp[0][i] =0;
break;
}
}
for(int i = 1; i<m; i++){
if(mase[i][0] != 2 ){
if(mase[i][0] == 1){
dp[i][0] = dp[i - 1][0] + 1;
}
else{
dp[i][0] = dp[i - 1][0] + 2;
}
}
else{
dp[i][0] = 0;
break;
}
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n;j++){
if(mase[i][j] != 2){
if(dp[i][j - 1]!=0 && dp[i - 1][j]!=0){
int value = mase[i][j] == 1? 1 : 2;
dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + value;
}
else if(dp[i][j - 1]!=0){
int value = mase[i][j] == 1? 1 : 2;
dp[i][j] = dp[i][j - 1] + value;
}
else if(dp[i - 1][j]!=0){
int value = mase[i][j] == 1? 1 : 2;
dp[i][j] = dp[i - 1][j] + value;
}
}
else{
dp[i][j] = 0;
}
}
}
System.out.println(dp[m - 1][n - 1]);
}
}
相关推荐
查看20道真题和解析
点赞 评论 收藏
分享
