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]);
}
}
相关推荐
10-23 16:33
门头沟学院 Java 
千千倩倩：同27给点建议，现在这个时间点可以快速看完外卖和点评，不用跟着敲，但一定要在看的时候总结每个部分的整个业务流程，对其中的实现有一个大概的印象。然后直接开始看八股，刷算法。八股和算法最好还是在项目学习中穿插着看。如果计算机基础，算法这些基础好，加上每天刻苦学习，两周可以达到勉强能面试的水平，到时候就直接海投中小厂，在约面和面试的过程中不断巩固知识。没找到实习也没关系，就当积累经验。再沉淀一波直接明年三月开始投暑期，毕竟是9本，总是有面试机会的，只要你这三个月不懈怠，面试发挥得一定不错，只要拿到一个中，大厂暑期实习，秋招就有竞争力了。总得而言，现在还有机会，但是时间非常紧张，需要你结合自己情况考虑，共勉
点赞 评论 收藏
分享
查看12道真题和解析 
点赞 评论 收藏
分享
投递大连飞创信息技术有限公司等公司10个岗位