【python练习】在棋盘上收集奖品，跟着书本理思路

在棋盘上收集奖品

Description

在棋盘上收集奖品。假设有一个m x n的棋盘，每个格子里有一个奖品（每个奖品的价值在10到1000之间），现在要求从左上角开始到右下角结束，每次只能往右或往下走一个格子，所经过的格子里的奖品归自己所有。问最多能收集价值多少的奖品。

图片1.png


Input
第一行：m n（5<=m,n<=14)，后面m行，每行n个整数(10,1000之间）。


Output
整数


Sample Input 1 

6 6
364 674 305 122 756 593
178 326 451 678 118 607
692 401 952 898 878 509
348 755 820 828 896 771
532 247 233 480 880 226
240 620 913 797 236 834
Sample Output 1

7389
Source

中学生可以这样学Python，P188例8-20
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
31

当m=1 n=3，一行一列时候，print(f(qipan,0,2))
a=0 不符合if条件，返回f(qipan,-1,2)和f(qipan,0,1)的最大值+qipan[0][2]
f(qipan,-1,2) 符合if条件，返回0，肯定比f(qipan,0,1)小
现在是f(qipan,0,1)+qipan[0][2]
f(qipan,0,1)不符合if条件，返回f(qipan,-1,1)和f(qipan,0,0)的最大值+qipan[0][1]
f(qipan,-1,1)符合if条件，返回0，肯定比f(qipan,0,0)小
现在是f(qipan,0,0)+qipan[0][1]
f(qipan,0,0)不符合if条件，返回f(qipan,-1,0)和f(qipan,0,-1)的最大值+qipan[0][0]
f(qipan,-1,0)和f(qipan,0,-1)符合if条件，返回0
结论：一行三列就是0+qipan[0][0]+qipan[0][1]+qipan[0][2]

m,n=map(int,input().split())
qipan=[]
for i in range(m):
    line=list(map(int,input().split()))
    qipan.append(line)
#print(qipan)

def f(qipan,a,b):
    if a<0 or b<0:
        return 0
    else:
        return max(f(qipan,a-1,b),f(qipan,a,b-1))+qipan[a][b]
print(f(qipan,m-1,n-1))

1
2
3
4
5
6
7
8
9
10
11
12
13
14