一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 636|回复: 12
收起左侧

[Leetcode] 关于DP

[复制链接] |试试Instant~ |关注本帖
zh355245849 发表于 2015-7-31 21:54:58 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 zh355245849 于 2015-7-31 22:00 编辑

最近刷有关DP的题目,感觉好费力。。。状态转移方程是怎么求出来的啊。。。比如下面这个。。。Maximal SquareThis problem can be solved by dynamic programming. The changing condition is:
t[j] = min(t[j-1], t[i-1][j], t[i-1][j-1]) + 1. It means the square formed before this point.

DK_BurNing 发表于 2015-8-1 00:06:20 | 显示全部楼层
感觉画图对理解题目很重要,尤其是这种Matrix类的题。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

354886 发表于 2015-7-31 23:19:56 | 显示全部楼层
这道题就是形成一个方形有三种情况,从同一行上一个;同一列上一个;左对角线上一个。那么这个新的方形的边长就应该是这三种情况的最短的那个再加上新的这个点。为什么是最小值呢,因为三种情况如果取最大值也许并不能形成方形,也就是说必须是最小值,就是必须是最苛刻那个边形成的方形才能往下继续。可以画图理解。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

水逼一枚 发表于 2015-8-3 14:54:52 | 显示全部楼层
楼主这个题目首先状态定义这一块儿有啥问题没?或者说思考的时候有啥障碍没?
回复 支持 反对

使用道具 举报

虾米酱 发表于 2015-8-3 17:27:18 | 显示全部楼层
画图可以看出 ,要想看当前所在位置能形成的最大正方形的边长,如果这一点本身是0就 pass,如果是1 的话就得往前看,要保证形成正方形则得看同一行前一个,同一列前一个,对角线前一个能形成的正方形边长,因为不能含有0,所以得取最小值,加上当前位置,所以+1. 有挺多讲 DP的博客的,你可以把几个题一起看,相似的还有 maximal triangle

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| zh355245849 发表于 2015-8-3 19:43:56 | 显示全部楼层
水逼一枚 发表于 2015-8-3 14:54
楼主这个题目首先状态定义这一块儿有啥问题没?或者说思考的时候有啥障碍没?

现在的状态就是很多题目照着画发现确实是对的。。。但是叫我自己写写不出来啊。。。
回复 支持 反对

使用道具 举报

虾米酱 发表于 2015-8-3 22:56:16 | 显示全部楼层
zh355245849 发表于 2015-8-3 19:43
现在的状态就是很多题目照着画发现确实是对的。。。但是叫我自己写写不出来啊。。。

其实我之前也是,多做做吧,应该会慢慢好起来,同加油

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-8-4 01:02:44 | 显示全部楼层
本帖最后由 水逼一枚 于 2015-8-4 02:02 编辑
zh355245849 发表于 2015-8-3 19:43
现在的状态就是很多题目照着画发现确实是对的。。。但是叫我自己写写不出来啊。。。

我的思考过程是这样的。你看看对你有没有帮助。先说状态定义。
最初考虑状态定义为dp{i}{j}表示从{0}{0}到{i}{j}的矩形内的最大square的面积area (即定义成问题本身), 这样定义后我们来分析状态转移方程如何写,首先大状态是dp{i}{j}, 显然我们要考虑的一个关键cell是{i}{j}, 如果nums{i}{j}= 0, 则我们知道这个元素的加入一定不会产生更大的square, 因此dp{i}{j} = Math.max( dp{i}{j-1}, dp{i-1}{j}); 如果nums{i}{j} = 1, 那么这个1的加入有可能会产生更大的square也有可能不会产生更大的square. 因此,我们要去判断这个1的加入是否能够组成新的更大的连续为1的边长,但是由于之前的状态记录的是从{0}{0}到某个点的matrix内的最大square面积而并非具体边长是否连续为1的情况,因此我们确定大状态由小状态过来的解的时候似乎还要去遍历元素,这样会造成时间复杂度的增加和问题的复杂性,因此我们考虑换一种状态定义方式。我们再分析一下,每一次子阶段的推进实际上都是考虑某一个点的加入,事实上一个点的加入和square area之间关系并不是最直接的关系,而是经过了一个桥梁就是边长 (因为很直观的推理是一个点的加入最先影响到边长是否有变化),再通过边长去影响square area. 因此,我们重新定义状态dp{i}{j}表示以nums{i}{j}为最右下角元素的全1正方形square的最大边长,这样定义才能把跟之前的连续边长关联起来,其实这是一类问题。就是以某个点为结尾的问题本身定义!!而不是直接以问题本身定义!!类比Lintcode #76 Longest Increasing Sequence题目。然后我们再来讨论状态转移方程,讨论nums{i}{j}为1和为0的两种情况。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2015-8-4 01:16:12 | 显示全部楼层
If you can't understand, maybe Try to recite some DP solutions first ?  From my experience, after reciting several DP, I could easily come up with similar solutions. I don't know the mechanism but it does work.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-4 01:54:48 | 显示全部楼层
水逼一枚 发表于 2015-8-4 01:02
我的思考过程是这样的。你看看对你有没有帮助。先说状态定义。
最初考虑状态定义为dp[j]表示从[0][0]到[ ...

嘿嘿,你们都没发现 中括号i中括号 其实是斜体标签么?italics
要表示下标请用DP{i}{j}这样的形式。
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-8-4 01:59:22 | 显示全部楼层
zhuli19901106 发表于 2015-8-4 01:54
嘿嘿,你们都没发现 中括号i中括号 其实是斜体标签么?italics
要表示下标请用DP{i}{j}这样的形式。

卧槽!还真是!我赶紧改一下免得误导楼主了。
回复 支持 反对

使用道具 举报

 楼主| zh355245849 发表于 2015-8-4 21:23:25 | 显示全部楼层
谢谢楼上的各位了!
回复 支持 反对

使用道具 举报

zzpnm003 发表于 2015-8-6 05:28:16 | 显示全部楼层
楼主你dp不好理解的从一维knapsack 问题做起,能慢慢理解,memory table和状态转移是怎么一回事。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表