【leetcode】221. さいだい正方形ダイナミックプランニングほう

0と1からなる2次元行列内で,1のみを含む最大正方形を見つけ,その面積を返した。

  :

  : 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

  : 4

動的プランニング分析:

dp(i,j)dp(i,j)dp(i,j)を用いて(i,j)(i,j)(i,j)を右下角とし,111の正方形の辺長最大値のみを含むことを示した.すべてのdp(i,j)dp(i,j)dp(i,j)dp(i,j)の値を計算できれば,その最大値は行列に111しか含まれない正方形の辺長最大値であり,その平方は最大正方形の面積である.
この位置の値が000である場合、dp(i,j)=0 dp(i,j)=0 dp(i,j)=0は、現在の位置が111からなる正方形にあることが不可能であるためである.
この位置の値が111である場合、dp(i,j)dp(i,j)dp(i,j)の値は、その上方、左方、左上の3つの隣接位置のdpdp値によって決定される.具体的には、現在位置の要素値は、3つの隣接位置の要素の最小値プラス111に等しく、状態遷移方程式は以下の通りである.
dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1 dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
js解法:

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
    if (!matrix.length || !matrix[0].length) return 0
    var maxSlideLen = 0, //     
        dp = Array(matrix.length); //  dp  

    for (var i = 0; i < matrix.length; i++) {
        dp[i] = Array(matrix[0].length).fill(0); //      0
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] === 1) {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1; //         dp  1
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 //    ，  ，     0
                }
                maxSlideLen = Math.max(maxSlideLen, dp[i][j]) //      
            }
        }
    }
    return maxSlideLen ** 2 //       
};