1

我一直在尝试 Topcoder 上的 dp 教程。为练习提供的问题之一是MiniPaint。我想我已经部​​分解决了 - 找到最小的没有。给定编号的误涂数。笔画，对于每一行，然后计算整个图片（再次使用 dp，类似于背包问题）。但是，我不确定如何计算最小值。没有每一行。

PS我后来找到了匹配编辑，但是找到了最小值的代码。不。每行的误绘似乎是错误的。有人可以准确解释他们在代码中做了什么吗？

4

2 回答 2

0

给定可用于绘制它的笔画量，该stripScore()函数返回每行的最小错误绘制数。虽然我不确定这个论点是否正确，但想法是从特定行开始，可以使用的笔划数量和直接在它之前的区域的颜色。rowidstartneeded

该算法的关键在于，第 k 个区域右侧区域的最佳得分由所需的笔画数和用于绘制第 (k-1) 个区域的颜色唯一确定。

于 2013-02-09T02:23:21.507 回答
0

直觉

我连续 3 天一直在用这个问题抨击我的头，没有意识到它需要连续使用两次动态编程逻辑。与 topcoder 提供的方法相比，我的方法是自下而上的。首先，我不会计算我可以实现的最小错误绘制数，而是计算我可以使用strokes绘制的最大单元格数maxStrokes。通过从矩阵的总单元格中减去我的发现，可以很容易地计算出结果。但我怎么能真正做到呢？最初的观察必须是每一行都可以为我提供一些绘制的单元格以换取一些笔画。这不依赖于其余的行. 这意味着，对于每一行，我可以计算我可以在该特定行上绘制的最大单元格数，以及一定数量的笔画。

例子

Input =['BWWWB','WBWWW'], maxStrokes =3
现在让我们看看第一行 BBWWB，并将 C 表示为我可以用 Q 笔画
Q C
0 0 的最大单元格数（我不能用 0 笔画)
1 3 ( BB WW B )
2 4 ( BBWW B)
3 5 ( BBWWB )
我们可以很容易地用一个长度为 4 的数组来表示上述结果，该数组为每个索引（笔画）存储可以绘制的最大单元数，即[0,3,4,5]
很容易看出第二行以相同的方式会有一个数组[0,4,4,5]。

现在可以仅通过这两个数组轻松计算结果，因为我们正在寻找的是两个选择的组合，每个计算数组一个，这将产生我可以用 3 次笔画绘制的最多的单元格。我的选择是什么？我的数组中的每一项都代表我可以用索引笔画绘制的最大单元格数。因此，对于第一个数组，一个选择是用 2 个笔划绘制 4 个单元格。然后我可以将该选择与第二个数组的第一个项目 4 结合起来，这意味着我可以用 1 个笔划绘制 4 个单元格。我的最终结果将是 4+4=8 个单元格，2+1=3 个笔划，这恰好是我能得到的最好结果。然后输出将微不足道地是 2*5-8=2 最小误绘。但是，我们需要找到一种最佳方法来计算不同的组合每行的项目以及它们可以给我带来的总和。

过程

我算法的第一部分填充了两个非常重要的表。让我们用N, M表示给定矩阵的维度。第一个表dp是一个N*M*maxStrokes矩阵。dp[i][j][k]表示我可以用 k 笔画从第 0 个单元格到第 i 行的第 j 个单元格绘制的最大单元格数。至于 maxPainted 表，那是一个 N*maxStrokes 矩阵。maxPainted[i][k]存储我可以用 k 笔画在第 i 行中绘制的最大单元格数，并且与上面示例中计算的数组相同。为了计算后者，我需要先计算dp。公式如下：

dp[i][j][k]= MAX (1,dp[i][r][k]+1 (if A[i][j]==A[i][r]) ,dp[i][r][k-1]+1 (if A[i][j]!=A[i][r]))，对于每 0<=r<j
可以翻译为：我可以用 k 笔画到第 i 行的第 j 个单元格的最大单元格数是：

  • 1，因为我可以忽略所有以前的单元格，单独绘制这个单元格
  • dp[i][r][k]+1, 因为当A[i][j]==A[i][r], 我可以不用额外的笔画来扩展那个颜色
  • dp[i][r][k-1]+1, 因为什么时候A[i][j]==A[i][r], 我得用新的笔画来画A[i][j]

现在很明显，dp需要计算表格以获得每行的最佳可能场景，即我可以使用每个可能的可用笔划数绘制的最大单元格数。maxPainted但是，一旦我计算了表格以得到我的结果，我该如何利用它呢？

我的方法的第二部分使用0-1 背包maxStrokes问题的变体来计算我可以使用可用笔划绘制的最大单元数。真正让这件事变得具有挑战性的是，与经典的背包相比，我只能从每一行中选择一项，然后计算所有可能的组合，这些组合不超过所需的笔划限制。为了实现这一点，我将首先创建一个长度为N*M +1的新数组，称为possSums. 让我们用达到总和SpossSums[S]所需的最小笔划数来表示。我的目标是计算每一行对这个数组的贡献。让我们用前面的例子来演示一下。

所以我有一个 2*5 输入，因此该possSums数组将由 10+1 个元素组成，我们将其设置为Infinity，因为我们试图最小化达到所述总和所需的击键次数。
所以，possSums= [0,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞]，第一项是 0 因为我可以用 0 笔画绘制 0 个单元格。我们现在要做的是计算每一行对 possSums 的贡献。这意味着对于我maxPainted数组的每一行，每个元素都需要提供一个特定的总和，这将模拟它被选择。正如我们之前演示的那样，maxPainted[0]= [0,3,4,5]. 这一行的贡献必须允许 0,3,4 和 5 作为我的 possSums 数组中可实现的总和，使用的笔画分别为 0,1,2,3。然后 possSums 将被转换为possSums= [0,∞,∞,1,2,3,∞,∞,∞,∞,∞]。下一行是maxPainted[1]= [0,4,4,5]，现在必须再次更改 possSums 以允许通过选择每个项目进行组合。请注意，每个更改都需要与同一行中的其他更改无关。例如，如果我们首先允许通过选择 的第一项来实现sum=4maxPainted[1]，则sum=9不能通过进一步选择同一个数组的 3d 项目来允许，这本质上意味着不能考虑同一行中项目的组合。为了确保不考虑此类情况，我为每一行创建了我的possSums数组的一个克隆，我将对它进行必要的修改，而不是我的原始数组。在考虑了 中的所有项目之后maxPainted[1]，possSums 看起来像这样possSums= [0,∞,∞,1,1,3,∞,2,3,4,6]，这给了我可以绘制的最大单元格数在第 8 个索引上最多 3 个笔划（总和 = 8）。因此我的输出将是 2*5-8=2

var minipaint=(A,maxStrokes)=>{
    let n=A.length,m=A[0].length
    , maxPainted=[...Array(n)].map(d=>[...Array(maxStrokes+1)].map(d=>0))
    , dp=[...Array(n)].map(d=>[...Array(m)].map(d=>[...Array(maxStrokes+1)].map(d=>0)))
    for (let k = 1; k <=maxStrokes; k++) 
        for (let i = 0; i <n; i++) 
            for (let j = 0; j <m; j++) {               
                    dp[i][j][k]=1 //i can always just paint the damn thing alone
                    //for every previous cell of this row
                    //consider painting it and then painting my current cell j
                    for (let p = 0; p <j; p++)
                        if(A[i][p]===A[i][j]) //if the cells are the same, i dont need to use an extra stroke
                            dp[i][j][k]=Math.max(dp[i][p][k]+1,dp[i][j][k])                    
                        else//however if they are,im using an extra stroke( going from k-1 to k)
                            dp[i][j][k]=Math.max(dp[i][p][k-1]+1,dp[i][j][k])                    
                                      
                    maxPainted[i][k]=Math.max(maxPainted[i][k],dp[i][j][k])//store the maximum cells I can paint with k strokes
            }             
                
    //this is where the knapsack VARIANT happens: 
    // Essentially I want to maximize the sum of my selection of strokes 
    // For each row, I can pick maximum of 1 item. Thing is,I have a constraint of my total
    // strokes used, so I will create an array of possSums whose index represent the sum I wanna reach, and values represent the MINIMUM strokes needed to reach that very sum. 

    // so possSums[k]=min Number of strokes needed to reach sum K 
    let result=0,possSums=[...Array(n*m+1)].map(d=>Infinity)
    
    //basecase, I can paint 0 cells with 0 strokes
    possSums[0]=0
    for (let i = 0; i < n; i++) {
        let curr=maxPainted[i],
            temp=[...possSums]// I create a clone of my possSums,
            // where for each row, I intend to alter It instead of the original array
            // in order to avoid cases where two items from the same row contribute to 
            // the same sum, which of course is incorrect.

        for (let stroke = 0; stroke <=maxStrokes; stroke++) {
            let maxCells=curr[stroke]           
            //so the way this happens is : 
            for (let sum = 0; sum <=n*m-maxCells; sum++) {
                let oldWeight=possSums[sum]//consider if UP until now, the sum was possible
                if(oldWeight==Infinity)// if it wasnt possible, i cant extend it with my maxCells
                    continue;
                // <GAME CHANGER THAT ALLOWS 1 PICK PER ROW 
                let minWeight=temp[sum+maxCells]//now, consider extending it by sum+maxCells

                // ALTERING THE TEMP ARRAY INSTEAD SO MY POTENTIAL RESULTS ARE NOT AFFECTED BY THE 
                // SUMS THAT WERE ALLOWED DURING THE SAME ROW 
                temp[sum+maxCells]=Math.min(minWeight,oldWeight+stroke)
                
                if(temp[sum+maxCells]<=maxStrokes)
                    result=Math.max(result,sum+maxCells)    
            }
        }
        possSums=temp
    }
    return n*m-result // returning the total number of cells minus the maximum I can paint with maxStrokes
}

于 2020-09-10T05:39:38.787 回答