面试题47(剑指offer)--礼物的最大值
题目： 在一个 m*n 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿各种里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？
【面试题47(剑指offer)--礼物的最大值】思路：
动态规划，dp[i][j]表示从左上角移动到(i,j)时，最大礼物价值。由于只能向右或者向下，则dp[i][j]的值就是左边一个和上边一个中的最大值，再加上当前values[i][j]的值,即dp[i][j] = Math.max(left, up) + values[i][j]。
代码：
private static int getMaxVal(int[][] values, int rows, int cols) {
if (values == null || rows <= 0 || cols <= 0) {
return -1;
}
int[][] dp = new int[rows][cols];
for (int i = 0;
i < rows;
i++) {
for (int j = 0;
j < cols;
j++) {
int left = 0;
int up = 0;
if (i > 0) {
left = dp[i - 1][j];
}
if (j > 0) {
up = dp[i][j - 1];
}
dp[i][j] = Math.max(left, up) + values[i][j];
}
}
return dp[rows - 1][cols - 1];
//返回礼物最大值
}
推荐阅读
- PMSJ寻平面设计师之现代(Hyundai）
- 杜月笙的口才
- Linux下面如何查看tomcat已经使用多少线程
- 皮夹克
- 解读《摩根集团》（1）
- 绘本与写作
- 蓝桥杯试题
- 麦田社群
- 面对苦难——如何化解
- 葱爷说股20190107