动态规划算法 [英] Dynamic Programming algorithm

问题描述

由于 0 和 1 N×M个的矩阵C>。如果鼠标是present在 [I：J] 那么这将是 1 ，否则这将是 0 。我们必须从开始[0：0] ，达到 [N-1：M-1] 。我们可以往下走或向右而已。鼠标在位置 [I：J] 会吓唬我们，如果我们通过一个位置 [X：Y] 这样的该 |九| + | JY |＆LT; = 1

Given a matrix of size NxM of 0 and 1. If a mouse is present at [i:j] then it would be 1, otherwise it would be 0. We have to start from [0:0] and reach [n-1:m-1]. We can go down or right only. A mouse at position [i:j] will scare us if we pass through a position [x:y] such that |i-x|+|j-y|<=1.

在其中找到我们通过不同的小鼠的最小数目吓的路径。心灵字不同的，即如果已经把我们吓得够呛那么它将不会再吓我们一个鼠标。

Find a path in which we are scared by minimum number of distinct mice. Mind the word distinct i.e. a mouse if has scared us then it won't scare us again.

这个问题被问在采访。我试图通过一般的DP问题所用的想法来解决它，我们可以向下移动，右，并必须找到最小的路径，但在所有这些问题，我们可以采取最低的[I-1：J- ] 和 [我：J-1] 来找到当前指数最小值和工作了所有的行从左至右

This question was asked in an interview. I tried to solve it by the idea used in general DP problem where we can move down and right and have to find the minimal path, but in all those problems we can take minimum of [i-1:j] and [i:j-1] to find current index minimum and work down all the rows from left to right.

但我不能在这里使用这个主意，因为这里鼠标特效4个细胞。

But I am not able to use this idea here, since here a mouse effects 4 cells.

有人给这个想法这可怎么解决呢？

Can someone give the idea how this can be solved?

推荐答案

我觉得非常简单的想法（这可能是不完全的，但足以满足面试官）如下。

I think the very simple idea (which is probably not complete but is good enough to satisfy an interviewer) is the following.

我们赋予权重的边缘。首先，所有的边都重0，然后考虑鼠标在顶点A.顶点有4个相邻的边B，C，D，E这与顶点B，C，D，E（连接的情况下，当一个一个只有2个或3相邻边是相似的）。所以，现在我们增加体重1相邻顶点B，C，D，E，除了边缘B，C，D，E逢缘。现在顶点A增加了重量2到每一个最小的重量路径，由顶点A惊。一个特殊的考虑是必要的任何可能的4角的小鼠，在这里我们可以通过增加2边权

We assign weights to edges. First, all edges have weight 0. Then consider a mouse in the vertex A. Vertex A has 4 adjacent edges b,c,d,e which connect A with vertices B,C,D,E (case when A has only 2 or 3 adjacent edges is similar). So now we increase weight by 1 for every edge adjacent to vertices B,C,D,E except edges b,c,d,e. Now vertex A adds weight 2 to every MINIMAL weight path "scared by vertex A". A special consideration is needed for any of possible 4 angular mice, where we can increase edge weights by 2.

现在我们已经在寻找一个整数格与下/右移动的最小重量路径的最简单的DP问题。 我担心的是关于被分离的，只有1或2个步骤的小鼠。我赶紧查了，这似乎工作，但我没有一个完整的证明。

Now we have a simplest DP problem of finding a path of minimal weight in an integer lattice with down/right moves. My concern is about mice which are separated with only 1 or 2 steps. I quickly checked, and this seems to work, but I don't have a complete proof.

这篇关于动态规划算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！