本文共 510 字，大约阅读时间需要 1 分钟。

题目描述

在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束。给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘

1    10   3    812   2    9    65    7    4    113    7    16   5

礼物的最大价值为 1+12+5+7+7+16+5=53。

解题思路

应该用动态规划求解，而不是深度优先搜索，深度优先搜索过于复杂，不是最优解。程序代码如下：

package cn.cqu.edu;public class Bonus {		public int getMost(int[][] board) {				if(board==null)		{			return 0;		}					int row=board.length;		int col=board[0].length;				if(row==0 || col==0)		{			return 0;		}				int[][] result=new int[row][col];				for(int i=0;i

转载地址：http://nckmi.baihongyu.com/