关于DP

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

感觉画图对理解题目很重要，尤其是这种Matrix类的题。

这道题就是形成一个方形有三种情况，从同一行上一个；同一列上一个；左对角线上一个。那么这个新的方形的边长就应该是这三种情况的最短的那个再加上新的这个点。为什么是最小值呢，因为三种情况如果取最大值也许并不能形成方形，也就是说必须是最小值，就是必须是最苛刻那个边形成的方形才能往下继续。可以画图理解。

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的两种情况。

楼主这个题目首先状态定义这一块儿有啥问题没？或者说思考的时候有啥障碍没？

画图可以看出 ，要想看当前所在位置能形成的最大正方形的边长，如果这一点本身是0就 pass,如果是1 的话就得往前看，要保证形成正方形则得看同一行前一个，同一列前一个，对角线前一个能形成的正方形边长，因为不能含有0，所以得取最小值，加上当前位置，所以+1. 有挺多讲 DP的博客的，你可以把几个题一起看，相似的还有 maximal triangle

水逼一枚 发表于 2015-8-3 14:54
楼主这个题目首先状态定义这一块儿有啥问题没？或者说思考的时候有啥障碍没？

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

zh355245849 发表于 2015-8-3 19:43
现在的状态就是很多题目照着画发现确实是对的。。。但是叫我自己写写不出来啊。。。

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

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.

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

嘿嘿，你们都没发现 中括号i中括号 其实是斜体标签么？italics
要表示下标请用DP{i}{j}这样的形式。