華為筆試——C++平安果dp演算法

 題目：平安果

題目介紹：給出一個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 }

結果如下圖所示：