【免费】数据结构和算法题解-1000多页.pdf_经典算法题解资源-CSDN文库

需积分: 0 117 浏览量 2021-05-09 22:27:49 上传评论 1 收藏 98.21MB PDF 举报

资源推荐

资源详情

资源评论

前言

大家好，我是博哥，连续3年多的时间坚持在微信公众号“数据结构和算法”中写算法题，截止

到目前已经在公众号上发布了500多道算法题。现在我把部分算法题整理成PDF的格式，这样方便

大家阅读，有的可能时间比较久了，这里没有全部列出来。

最初写的时候代码都是截图，没法复制，后来写的是可以复制的，等有时间了我在把代码全部整

理也会放到百度网盘中，和这个文档一起，大家可以下载运行，我目前使用的都是java语言，如

果想切换到其他语言，也可以对照代码进行修改。

当然学习的脚步不能停止，我还会继续在公众号上不断的输出各种算法题，欢迎大家阅读。如果

大家不小心把这个文档搞丢了也没关系，可以到我微信公众号中回复“pdf”即可获取下载地

址，我把文档放到了百度网盘上了。这个文档也会不停的更新，因为我公众号会不停的写算法

题，所以也会隔段时间同步到这个文档上，大家可以直接在我公众号中回复“pdf”获取最新的

文档即可。关于我微信公众号大家可以扫描下方二维码关注。如果觉得不错的，可以相互转发，

我们大家一起学习。感谢大家的支持。

V4.0

注意：文章之前都是图文结合的，后来有了

视频，视频没法在pdf中播放，如果想看视

频可以直接点击，会跳转到到我公众号中，

然后就可以观看了。

3 if (grid null || grid.length 0)

4 return 0;

5 int m = grid.length;

6 int n = grid[0].length;

7 int[][] dp = new int[m][n];

8 dp[0][0] = grid[0][0];

9 //初始化dp的最上面一行，从左到右累加

10 for (int i = 1; i < n; i++) {

11 dp[0][i] = dp[0][i - 1] + grid[0][i];

12 }

13 //初始化dp的最左边一列，从上到下累加

14 for (int i = 1; i < m; i++) {

15 dp[i][0] = dp[i - 1][0] + grid[i][0];

16 }

17

18 //下面是递推公式的计算

19 for (int i = 1; i < m; i++) {

20 for (int j = 1; j < n; j++) {

21 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

22 }

23 }

24 return dp[m - 1][n - 1];

25 }

为了方便计算我们还可以把 d p 的宽和高增加 1 ，也就是 d p 的最上面一行和最左边一列不

存储任何数值，他们都是0 ，这样是为了减少一些判断

1 public int maxValue(int[][] grid) {

2 if (grid == null || grid.length == 0)

3 return 0;

4 int m = grid.length;

5 int n = grid[0].length;

6 //为了方便计算，dp的宽和高都增加了1

7 int[][] dp = new int[m + 1][n+1];

8 //下面是递推公式的计算

9 for (int i = 0; i < m; i++) {

10 for (int j = 0; j < n; j++) {

11 dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];

12 }

13 }

14 return dp[m][n];

15 }

动态规划代码优化

我们来看一下这个公式

dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];

我们发现当前值只和左边和上边的值有关，和其他的无关，比如我们在计算第 5 行的时

候，那么很明显第 1 ， 2 ， 3 行的对我们来说都是无用的，所以我们这里可以把二维 d p 改

成一维的，其中 d p [ i ] [ j - 1 ] 可以用 d p[ j- 1] 来表示，就是当前元素前面的， d p[ i- 1] [j ] 可

以用 dp [j ]来表示，就是上边的元素。

剩余1013页未读，继续阅读

内容反馈

数据结构和算法

粉丝: 1w+
资源: 19

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip