博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[算法]年终奖
阅读量:6203 次
发布时间:2019-06-21

本文共 1066 字,大约阅读时间需要 3 分钟。

http://blog.csdn.net/baidu_20363843/article/details/49428909 0/1背包问题 动态规划 【转载:http://blog.csdn.net/codeemperor/article/details/51068478】

小东所在公司要发年终奖,而小东恰好获得了最高福利,他要在公司年会上参与一个抽奖游戏,游戏在一个6*6的棋盘上进行,上面放着36个价值不等的礼物,每个小的棋盘上面放置着一个礼物,他需要从左上角开始游戏,每次只能向下或者向右移动一步,到达右下角停止,一路上的格子里的礼物小东都能拿到,请设计一个算法使小东拿到价值最高的礼物。 

给定一个6*6的矩阵board,其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值,保证每个礼物价值大于100小于1000。

 

考察动态规划:

1 import java.util.*; 2  3 public class Bonus { 4     public int getMost(int[][] board) { 5         // write code here 6         int n = board.length; 7         int[][] dp = new int[n][n]; 8         dp[0][0] = board[0][0]; 9         for (int i = 1; i < n; i++) {           10                 dp[0][i] = dp[0][i-1]+board[0][i];11                 dp[i][0] =dp[i-1][0]+board[i][0];12 13         }14         for (int i = 1; i < n; i++) {15             for (int j = 1; j < n; j++) {16                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + board[i][j];17             }18         }19         return dp[n - 1][n - 1];20     }21 }

 

转载于:https://www.cnblogs.com/woshare/p/6940251.html

你可能感兴趣的文章
[C#]Attribute特性(3)——AttributeUsage特性和特性标识符
查看>>
Oracle分页存储过程
查看>>
Fast Image Cache – iOS 应用程序高性能图片缓存
查看>>
C#实现简单的 Ping 的功能,用于测试网络是否已经联通
查看>>
开源项目 配置管理软件推荐
查看>>
CentOS6.7-64bit编译hadoop2.6.4
查看>>
IntelliJ IDEA2017 修改缓存文件的路径
查看>>
无向图的点双连通分量(tarjan模板)
查看>>
关于Unity中UI中的Image节点以及它的Image组件
查看>>
神奇的图像处理算法
查看>>
java maven 操作 收集的一些命令
查看>>
springcloud-05-ribbon中不使用eureka
查看>>
SPOJ QTREE6 lct
查看>>
Java - 对象(object) 具体解释
查看>>
[.NET跨平台]Jexus独立版本的便利与过程中的一些坑
查看>>
swift菜鸟入门视频教程-09-类和结构体
查看>>
Oracle数据库备份恢复,巡检须要关注的对象设置以及相关恢复概述
查看>>
jQuery序列化表单为JSON对象
查看>>
使用malloc分别分配2KB的空间,然后用realloc调整为6KB的内存空间,打印指针地址...
查看>>
Redis 它是什么?它用来做什么?它的优势与短板如何?
查看>>