正文 

当前位置： 首页 > java > java教程

2017年华为优招机试题_平安果_编程题

author author     2022-09-09     281

关键词：

题目描述

简要描述： 给定一个M行N列的矩阵(M*N个格子)，每个格子中放着一定数量的平安果。

你从左上角的格子开始，只能向下或向右走，目的地是右下角的格子。
每走过一个格子，就把格子上的平安果都收集起来。求你最多能收集到多少平安果。
注意：当经过一个格子时，需要要一次性把格子里的平安果都拿走。
限制条件：1 < N, M <= 50；每个格子里的平安果数量是0到1000(包含0和1000)。

输入描述:

输入包括两行:
第一行为矩阵的行数M和列数N
第二行为一个M*N的矩阵，矩阵的数字代表平安果的数量，例如：
1 2 3 40
6 7 8 90

输出描述:

输出一个数字,表示能可以收集到的平安果的数量。

示例1

输入

2 4
1 2 3 40
6 7 8 90

输出

136

动态规划求解

解析：设dp[i][j]为走到i*j位置的路径长度，那么显而易见 dp[i][j] = Math.max(dp[i][j - 1] + num[i][j], dp[i - 1][j] + num[i][j]);

 

Java程序

import java.util.Scanner;

public class PingAnGuoDp

{

  public static void main(String[] args)

  {

    Scanner in = new Scanner(System.in);

    while (in.hasNext())

    {

      String s = in.nextLine();

      String[] str = s.split(" ");

      int M = Integer.parseInt(str[0]);

        if (M<=1||M>50)

      {

        break;

      }

      int N = Integer.parseInt(str[1]);

        if (N<=1||N>50)

         {

          continue;

         }

      int num[][] = new int[M][N];

 

      for (int i = 0; i < M; i++)

      {

         String st = in.nextLine();

         String[] strs = st.split(" ");

         for (int j = 0; j < strs.length; j++)

         {

          

           num[i][j] = Integer.parseInt(strs[j]);

          

           if(num[i][j]<0||num[i][j]>1000){

               ;

           }

         }

 

      }

      System.out.println(getMaxValue(num));

    }

  }

  /** 获得最多的平安果*/

  public static int getMaxValue(int[][] num)

  {

    int Row = num.length;

    int Col = num[0].length;

    int[][] dp = new int[Row][Col];

   

    /*

      dp[0][0]=num[0][0];

      for(int i=1;i<Row;i++) { dp[i][0]=dp[i-1][0]+num[i][0]; } //为DP第0行赋值

      for(int i=1;i<Col;i++) { dp[0][i]=dp[0][i-1]+num[0][i]; }

     */

   

    // DP第0列赋值

    for (int i = 0; i < Row; i++)

    {

      for (int j = 0; j <= i; j++)

      {

         dp[i][0]+= num[j][0];

      }

    }

   

    // DP第0行赋值

    for (int i = 0; i < Col; i++)

    {

      for (int j = 0; j <= i; j++)

      {

         dp[0][i] += num[0][j];

      }

    }

 

    for (int i = 1; i < Row; i++)

    {

      for (int j = 1; j < Col; j++)

      {

         dp[i][j] = Math.max(dp[i][j - 1] + num[i][j], dp[i - 1][j] + num[i][j]);

      }

    }

    return dp[Row - 1][Col - 1];

  }

}

c++程序

#include<iostream>

using namespace std;

#include<vector>

#include<queue>

typedef struct Pos

{

    int x;

    int y;

    Pos(int x,int y){this->x=x;this->y=y;}

} Pos;

 

int main()

{

         int row,column;

         cin>>row>>column;

         vector<vector<int>> grid(row,vector<int>(column,0));

         vector<vector<int>> map(row,vector<int>(column,0));

         for(int i=0;i<row;i++)

                   for(int j=0;j<column;j++)

                            cin>>grid[i][j];

    queue<Pos> q;

    q.push(Pos(0,0));

    map[0][0]=grid[0][0];

    while(!q.empty())

    {

        Pos p=q.front();

        int x=p.x,y=p.y;

        q.pop();

        if(x<grid.size()-1)

        {

            if(map[x+1][y]==0) q.push(Pos(x+1,y));

            map[x+1][y]=max(map[x][y]+grid[x+1][y],map[x+1][y]);

        }

           

        if(y<grid[0].size()-1)

        {

            if(map[x][y+1]==0)  q.push(Pos(x,y+1));

            map[x][y+1]=max(map[x][y]+grid[x][y+1],map[x][y+1]);

        }

    }

    cout<<map[grid.size()-1][grid[0].size()-1];

         return 0;

}



高分替兄弟求vb编程题

试题一：设计一个登陆窗体，如果用户输入正确密码和用户名，则进入另一窗体，否则利用消息框提示错误，三次错误即退出程序。试题二：制作一个标准WINDOWS界面，包括菜单、工具条、状态栏要求：菜单、工具条、状态栏内... 查看详情

003_c/c++笔试题_分享大汇总

(一)感谢：lhzstudio01_C++经典面试题全集50~100道都附带有参考答案02_C++开发工程师面试题库100~150道03_C++笔试题库之编程、问答题150~200道04_C++笔试题库之编程、问答题200~300道  查看详情

目录大纲

 Day34黏包Day33Socket编程.Day32网络编程Day31面向对象考试题第四次考试.Day30面向对象的考试题Day29_模块二-hashlib_configparse_loggingDay28面向对象的进阶-内置函数（__new__,__del__）Day34面试题Day27类的进阶-反射Day26封装Day25多态.Day24继承Da... 查看详情

科大讯飞笔试题_杀手(代码片段)

题目：　　有n个杀手排成一行，每个杀手都有一个不同的编号（编号1-n），在每个夜晚，杀手都会行动，如果某个杀手编号大于他右边的杀手的编号，他就会杀死他右边的杀手，杀手的行动是瞬间的，因此一个人可能某一个夜... 查看详情

2017年11月软考网络工程师上午试题解析一

 2017年11月软考网络工程师上午试题一（前10题）在程序的执行过程中，cache与主存的地址映射是由___（1）__完成。A操作系统程序员调度C硬件自动D用户软件解析：2011年重复考题    映像可分为全相联映像、直接... 查看详情

网易2017秋招编程题集合_以下代码全部来自牛客网

如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：{1,2,1},{15,78,78,15},{112}是回文序列, {1,2,2},{15,78,87,51},{112,2,11}不是回文序列。现在给出一个数字序列，允许使用一种转换操作：选择任意两个... 查看详情

rhcsa考证试题分析3(15-19)最后一题明天单独分析

16.NTP客户端连接配置你的系统，让其作为server1.example.com的NTP的客户端650)this.width=650;"src="https://s4.51cto.com/wyfs02/M02/9D/F2/wKiom1mJMDChVBxZAAZzv40BqR4005.png-wh_500x0-wm_3-wmp_4-s_3404263002.png"title="2017-08-0 查看详情

24th/dec/2017__21:00

　　今日是个重大的日子——平安夜到了！考试考完了！　　啦啦啦～～～　　唉，考试炸的一干二净，化学难的感人肺腑，幸亏运气好撞对了几个题，不过未来的日子还长着，继续努力`/（>o<）`/！　　不过话说啊，... 查看详情

cqoi2017试题泛做

Day14813:[Cqoi2017]小Q的棋盘树形背包DP。1#include<cstdio>23#definemaxn1104#defineRregister5#definecmax(_a,_b)(_a<(_b)?_a=(_b):0)6structEdge{7Edge*next;8intto;9}*last[maxn],e[maxn<<1],*ecnt=e;10i 查看详情

shoi2017试题泛做

一口气做完六个省的省选（误）Day1[Shoi2017]期末考试枚举最大的天数，然后代价贪心地O(1)计算。1#include<cstdio>2#include<algorithm>34#defineRregister5typedeflonglongll;6#definemaxn1000107#definecmax(_a,_b)(_a<(_b)?_a=(_b):0)8 查看详情

剑指offer_编程题_25

题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题... 查看详情

剑指offer_编程题_21

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。classSolutionpublic:voidpush(intvalue)st.push(value);voidpop()st.pop();inttop()returnst.top();intmin()intmin_num=st.top();while(!st.empty())inttmp=st.to 查看详情

剑指offer_编程题_19

题目描述输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵：12345678910111213141516则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10. classSolutionpublic:vector<int>printMatrix(vector<vector&l... 查看详情

剑指offer_编程题_23

题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。classSolutionpublic:boolVerifySquenceOfBST(vector<int>sequence)if(sequence.size()==0)re... 查看详情

前端期末考试试题及参考答案(03)

版权声明本文原创作者：谷哥的小弟作者博客地址：http://blog.csdn.net/lfdfhl一、填空题transition属性中______规定应用过渡的CSS属性的名称。transition属性中______定义过渡效果花费的时间。transition属性中______属性规定过渡效果... 查看详情

（面试题）python面试题集锦-附答案(代码片段)

1、一行代码实现1-100的和sum_1_100=sum(range(1,101))print(sum_1_100)#50502、如何在一个函数内修改全局变量的值a=100deffoo():globalaa=300foo()print(a)#3003、字典如何删除键和合并两个字典d1="name":"wj","age":22d2="male":"famle"#删除键deld1["name" 查看详情

剑指offer_编程题_1

题目描述在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 classSolutionpublic:boolFind(intt... 查看详情

剑指offer_编程题_4

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列1,2,4,7,3,5,6,8和中序遍历序列4,7,2,1,5,3,8,6，则重建二叉树并返回。/***De... 查看详情