C# · 12月 20, 2021

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

2 #include

3 using namespace std;

4 int main()

5 {

6 int m,n;

7 int i,j;

8 while (cin >> m >> n)

9 {

10 vector ivec(m,vector(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 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 }

结果如下图所示: