华为笔试——C++平安果dp算法
2018-09-01 05:38:26来源:博客园 阅读 ()
题目:平安果
题目介绍:给出一个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 }
结果如下图所示:
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash