首页 > 代码库 > 2017年华为优招机试题_平安果_编程题

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

题目描述

简要描述: 给定一个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;

}



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