題意:在一張字母的grid 圖,找出以(x,y)為正方形中心其最大的正方形可能,同時正方形裡為相同的字母
解法:利用dp,例:以(i,j) 為正方形左上找出最大的正方形可能。以同樣的手法分別找出
右上、左下、右下。
若以右下為底其dp公式為dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
文章標籤
全站熱搜
題意:在一張字母的grid 圖,找出以(x,y)為正方形中心其最大的正方形可能,同時正方形裡為相同的字母
解法:利用dp,例:以(i,j) 為正方形左上找出最大的正方形可能。以同樣的手法分別找出
右上、左下、右下。
若以右下為底其dp公式為dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1