手把手教你dp：摘花生问题（递归改动态规划DP）_花生问题的动态规划

dp系列

手把手教你dp：01背包问题（递归改动态规划DP）
手把手教你dp：摘花生问题（递归改动态规划DP）
手把手教你dp：蓝桥杯-地宫寻宝（递归改动态规划DP）

1 摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

输入格式
第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

数据范围
1≤T≤100,
1≤R,C≤100,
0≤M≤1000
输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16

2 递归求解

2.1 思路

每到一个位置都会拿到相应的花生，只能选择向下或者向右走，因此，最佳的方案是取向下走和向右走的最大值

2.2 递归函数代码

int process(int curX, int curY){
    if(curX > R || curY > C) return 0; //越界返回0
    if(curX == R && curY == C) return s[R][C];//到达出口
    return W + s[curX][curY] + max(process(curX + 1, curY), process(curX, curY + 1));
}
1
2
3
4
5

2.3 递归版本完整代码

#include <iostream>

using namespace std;
const int N = 110;
int T, R, C, W;
int s[N][N];

int process(int curX, int curY){
    if(curX > R || curY > C) return 0;
    if(curX == R && curY == C) return s[R][C];
    return W + s[curX][curY] + max(process(curX + 1, curY), process(curX, curY + 1));
}

int main()
{
    cin >> T;
    while(T--){
        cin >> R >> C;
        for(int i = 1; i <= R; i++){
            for(int j = 1; j <= C; j++){
                cin >> s[i][j];
            }
        }
        cout << process(1, 1) << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3 递归改动态规划

3.1 思路

（1）确定dp表的维度，不难发现对于任意一个状态需要curX、curY来确定，因此dp表是二维的。
（2）确定各个维度的取值范围：
curX：[1, R]
curY：[1,C]
（3）确定目标值在dp表中的位置
目标值即上述调用递归函数所传的初始值：dp[1][0]
（4）根据递归终止条件，确定dp表的初始状态：
根据终止条件确定dp表的初始状态如下

if(curX > R || curY > C) return 0;
if(curX == R && curY == C) return s[R][C];
1
2

因此当curX > R || curX > C dp[curX][curY] = 0；
当curX == R && curY == C dp[curX][curY] = s[R][C]
5）确定状态转移方程：
完全可以由上述递归函数代码得出：

return W + s[curX][curY] + max(process(curX + 1, curY), process(curX, curY + 1));
1

dp[i][j] += max(dp[i+1][j], dp[i][j+1])

3.2 dp表求解代码

for(int i = R + 1; i >= 1; i--) s[i][C+1] = 0;
for(int j = C + 1; j >= 1; j--) s[R+1][j] = 0;
for(int i = R; i >= 1; i--){
    for(int j = C; j >= 1; j--){
        if(i == R && j == C) continue;
        s[i][j] += max(s[i+1][j], s[i][j+1]);
    }
}
1
2
3
4
5
6
7
8

3.3 dp完整代码

#include <iostream>

using namespace std;
const int N = 110;
int T, R, C, W;
int s[N][N];

int main()
{
    cin >> T;
    while(T--){
        cin >> R >> C;
        for(int i = 1; i <= R; i++){
            for(int j = 1; j <= C; j++){
                cin >> s[i][j];
            }
        }
        for(int i = R + 1; i >= 1; i--) s[i][C+1] = 0;
        for(int j = C + 1; j >= 1; j--) s[R+1][j] = 0;
        for(int i = R; i >= 1; i--){
            for(int j = C; j >= 1; j--){
                if(i == R && j == C) continue;
                s[i][j] += max(s[i+1][j], s[i][j+1]);
            }
        }
        cout << s[1][1] << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

4 递归改dp的步骤

（1）dp表的维度：即状态由几个变量唯一确定。
（2）确定表的各个维度的取值范围。
（3）确定目标值在dp表中的位置。
（4）根据递归终止条件，确定dp表的初始状态。
（5）确定dp表中任意一个位置的值与表中其他位置的依赖关系，即状态转移方程。