leetcode之动态规划 medium部分

发表于

算法学习过程中动态规划的medium部分，动态规划好难啊。

1277

题目描述

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

题目解析

给定一个矩阵，矩阵中元素的数值是0或者1，统计矩阵中全部由1组成的正方形的个数。单独一个为1的元素可以看作是一个边长为1的正方形。运用动态规划的思想，dp[i][j]是以matrix[i][j]为右下角的正方形的个数，一直搞不清楚dp[i]][j]与dp[i][j-1]、dp[i-1][j]、dp[i-1][j-1]的关系。可以看参考链接里的讲解，首先看第一张图，在这张图中当dp[4][4] = 4时，给满足条件的区域染上深绿色，那么对于点(4,3)、(3,4)、(3,3)来说，它们都可以作为一个边长为3的正方形的右下角，dp[4][3]、dp[3][4]、dp[3][3]至少为3。所以可以得到下面的不等式：

1
2
3
dp[i][j-1] >= dp[i][j] - 1
dp[i-1][j] >= dp[i][j] - 1
dp[i-1][j-1] >= dp[i][j] - 1

综合以上三个不等式，得到下面这个不等式：

1
min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) >= dp[i][j] - 1

那么当固定dp[i-1][j]、dp[i][j-1]、dp[i][j]时，又可以得到dp[i][j]与它们的关系。当dp[3][3]、dp[3][4]、dp[4][3]中的最小值为3时，假如(4,4) = 1，那么(4,4)可以作为一个边长为4的正方形的右下角，所以dp[4][4]至少为4，所以可以得到：

1
dp[i][j] >= min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1

根据夹逼定理，综合两个不等式可以得到如下等式。

1
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1

以上等式成立的条件是(i,j) = 1且i,j均不为0时成立。当i=0或j=0时，(i,j)只能作为一个边长为1的正方形的右下角，dp[i][j] = martrix[i][j]；当(i,j)=0时，dp[i][j] = 0。综合各个情况，得到如下关系式：

1
2
3
当i=0或j=0时，dp[i][j] = martrix[i][j]；
当(i,j) = 0时，dp[i][j] = 0;
其他情况，dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) + 1。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        int res = 0;
        vector<vector<int>> dp(n, vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j] == 0)
                    dp[i][j] = 0;
                else if(i == 0 || j == 0)
                    dp[i][j] = matrix[i][j];
                else
                    dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1;
                
                res += dp[i][j];
            }
        }
        
        return res;
    }
};

参考

https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/solution/tong-ji-quan-wei-1-de-zheng-fang-xing-zi-ju-zhen-b/

877

题目描述

题目解析

给定偶数堆石头，Alex和Lee两个人分别从数组的头部或尾部拿走石头，因为石头总数是奇数，所以谁手里的石头多，谁获胜，Alex先拿，当Alex获胜时返回true。一直不会做这种游戏的题目，不知道该怎么表示整个过程，看到讨论区说直接返回true，参考的链接里给出了解释，因为给定数组的长度是偶数，但石头的总数是奇数，可以选择一直拿下标为偶数的石头堆，或一直拿下标为奇数的石头堆，因为石头的个数是奇数，那么以下标为奇数或偶数分出的两堆石头必然有一个多，一个少，因为Alex先拿，且两个人均发挥自己的最佳状态，那么按照这种方式取石头，则Alex肯定能赢。设piles.size=n，n是偶数，比如Alex一直拿偶数堆，首先Alex拿piles[0]，如果Lee拿piles[1]，那么Alex可以拿piles[2]，如果Lee拿piles[n-1]，那么Alex可以拿piles[n-2]。奇数堆同理。

1
2
3
4
5
6
7
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
        
    }
};

如果用动态规划的思想，dp[i][j]表示从第i堆到第j堆，当前选手相对于对手多出来的石子数，比如到了某一轮，石子还剩[piles[i],piles[i+1],piles[i+2],…,piles[j]]，那么对于Alex来说，他有两种选择：

  1. 拿piles[i]，那么dp[i][j] = piles[i] - dp[i+1][j]，因为此时石子只剩下第i+1堆到第j堆，Lee多于Alex的石子数就是dp[i+1][j]；
  2. 拿piles[j]，那么dp[i][j] = piles[j] - dp[i][j-1]，因为此时石子数只剩下第i堆到第j-1堆，Lee多于Alex的石子数就是dp[i][j-1]。
    因为选手都是发挥自己最佳的状态，那么dp[i][j]的递推关系式如下：
    1
    dp[i][j] = max(piles[i] - dp[i+1][j],piles[j] - dp[i][j-1])

当i == j时，就表示石头堆只剩一堆了，那么dp[i][j] = piles[i]，我们知道的就是每堆的石头数，也就是当i == j时的dp[i][j]的数值。

参考

https://blog.csdn.net/bengepai/article/details/82414227
https://cloud.tencent.com/developer/article/1446700