动态规划----二维DP问题

问题：平面上有N*M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始， 每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来， 这样下去，你最多能收集到多少个苹果。

简单的说，这个问题的步骤依然是找到状态与状态转移方程

状态：到（i，j）点时的苹果数

状态转移放厨房：s(i,j)=max{s(i-1,j),s(i,j-1)}+A(i,j)，其中s（i，j）是（i,j）点时苹果发总数，A是当前点的苹果数

案例：

 代码实现：

n = int(input())
m = int(input())a = []for i in range(n):b = []for j in range(m):b.append(int(input()))a.append(b)s = []for i in range(n):b = []for j in range(m):b.append(0)s.append(b)s[0][0] =  a[0][0]for i in range(n):for j in range(m):if i>0 and j>0:s[i][j] = a[i][j] + max(s[i-1][j],s[i][j-1])elif i>0 and j<=0:s[i][j] = a[i][j] + s[i-1][j]elif i<=0 and j>0:s[i][j] = a[i][j] + s[i][j-1]print(s)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！