• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

华为笔试——C++平安果dp算法

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

 题目:平安果

题目介绍:给出一个m*n的格子,每个格子里有一定数量的平安果,现在要求从左上角顶点(1,1)出发,每次走一格并拿走那一格的所有平安果,且只能向下或向右前进,最终到达右下角顶点(m,n),要求求出能拿走的平安果的最大数值。

输入:第一行有两个数值m,n,然后是m行n列数值。

输出:一个数值代表平安果的最大数量。

例:

输入:

4 4

1 2 4 8

10 14 3 9

17 6 7 20

12 5 21 23

输出:

89

分析:这是一种比较典型的dp算法(动态规划)的题目,每一格获取的平安果最大数值都与上格或左格有关(即交叠问题),且无后效性。这题也证明了动态规划可以解决贪心算法所解决不了的问题,若用贪心算法,不一定能得出总体最优解。

状态方程:dp[ i ][ j ]=max{ dp[ i-1 ][ j ] , dp[ i ][ j-1 ]}+A[ i ][ j ] 

代码如下:

 1 #include <vector>
 2 #include <iostream>
 3 using namespace std;
 4 int main()
 5 {
 6     int m, n;
 7     int i, j;
 8     while (cin >> m >> n)
 9     {
10         vector<vector<int>> ivec(m, vector<int>(n));
11         for (i = 0; i < m; ++i)
12         {
13             for (j = 0; j < n; ++j)
14             {
15                 cin >> ivec[i][j];
16             }
17         }
18         vector<vector<int>> dp(ivec);
19         for (i = 1; i < m; ++i)
20         {
21             dp[i][0] += dp[i - 1][0];
22         }
23         for (j = 1; j < n; ++j)
24         {
25             dp[0][j] += dp[0][j - 1];
26         }
27         for (i = 1; i < m; ++i)
28         {
29             for (j = 1; j < n; ++j)
30             {
31                 dp[i][j] += (dp[i - 1][j] < dp[i][j - 1]) ? dp[i][j - 1] : dp[i - 1][j];
32             }
33         }
34         cout << dp[m - 1][n - 1] << endl;
35     }
36     return 0;
37 }

结果如下图所示:


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
【转】C++中构造函数初始化发布时间:2022-07-14
下一篇:
C#多线程编程のTask(任务全面解析)发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap