算法(8)-动态规划DP-最长递增子序列、最大和/积子数组、下降路径最小

小陈同学-陈百万

1009人浏览 · 2020-09-12 20:51:06

小陈同学-陈百万 · 2020-09-12 20:51:06 发布

Abstract


base - 重复子问题、状态转移
// 509. 斐波那契数  -- 重复子问题 f(20) = f(19) + f(18) ,  f(19)拆解又需要重新解f(18), 用memo/dp数组来记住字问题的解，需要求解一个子问题时，先去看看适否以及有人解过了。
// 自顶向下(递归返回)、自低向上(循环迭代)、空间约简(只记录前两个状态)
int fib(int n)；
// 322. 零钱兑换 -- 状态转移-暴力递归(自顶向下)， for循环（自底向上） 
// k=1, 2, 5 求amount=11, 可拆解为三个子问题取min, min(a=10, a=9,  a=6), 这三个方案+1硬币都能变成原文题的一个方案 （最优子结构 <- 子问题独立 <-硬币数量没有限制）
// dp(n) 凑出amount为n的最少硬币数
int coinChange(vector<int>& coins, int amount);
// 暴力解法 - 与【39. 组合总和-(无重复-可复选-限和)】, 所有组合找最少硬币数

// 279. 完全平方数 -- n-1, n-4, n-9, dp[0] = 0, 
int numSquares(int n);


advanced - 一维 dp, 凡事只用到上一状态的都可以做空间约减, 子序列必然是双重for循环
// - 可空间约减
// 53. 大子数组和 - dp[i] 以nums[i]结尾的最大和 // 更新时，考虑的是dp[i-1]是否需要加进来，如果dp[i-1]>0加进来，最大和的长度一定比仅仅使用nums[i]之后的数字构成的和大，如果dp[i-1]<0,那么就仅从nums[i]重新开始构建最大和子数组。
int maxSubArray(vector<int>& nums);
// 152. 乘积最大子数组 - dp[i] 以nums[i]结尾的最大乘积， 同时需要维护最小积
int maxProduct(vector<int>& nums); 

// -不可空间约减
// 300.最长递增子序列 - dp[i] 以nums[i]结尾的，拥有最大的长度 递增子序列 的长度. dp[i]的更新信息来自于max[dp[0], dp[i-1]] + 1(如果能从新构成一个递增序列) 和 1（无法成为前序递增序列的一部分，自己重新开始）
int lengthOfLIS(vector<int>& nums)；
// 343. 整数拆分 dp[i] 来自于所有dp[1]-dp[i-1] 所有情况更新而来，选最大。关注dp[j]是否继续拆分的问题 
// 本质上是一维度dp, 但是当n太大时，dp数组开销太大，存在数学推导求解
int integerBreak(int n);


advanced - 二维 dp
// 931. 下降路径最小和 -- dp数组-从上到下从左到右，dp[i][j]初值设置为不能取到的最小值10001;
// 最后一行选一个最小值
int minFallingPathSum(vector<vector<int>>& matrix);
// 1143. 最长公共子序列 - 二维dp, dp[i][j]更新来自 dp[i-1][j-1]+1, max(dp[i][j-1], dp[i-1][j])三个方向。
int longestCommonSubsequence(string text1, string text2);
// # 221. 最大正方形 - 二维dp, dp[i][j]更新来自于min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1, 最大面积来自最小值+1，短板决定上限的体现。

相似、易混淆题
// 确实非常相似的题目, dp[i] == dp[j] 在一个序列里构成回文，两个序列里为公共序列,
// dp 矩阵的初始值设置有区别，
// 1143. 最长公共子序列 - 二维 DP, 初始化第0行第0列，从上往下，从左边往右
def longestCommonSubsequence(self, text1, text2);
// 516. 最长回文子序列 - 二维 DP,  初始化对角线，从下往上，从左往右边
def longestPalindromeSubseq(self, s);

动态规划 - Dynamic Programming, 常见于最值问题解题。

核心是穷举：穷举所有子问题，由子问题递推原问题题。需要将原问题拆解为子问题，子问题需要满足相互独立，暴力递归所有子问题的解-> 求最优 ->递推 ->得到原问题得到解

聪明的穷举：动态规划存在重叠子问题，如果暴力求解效率会很低，所以在穷举所有可能解的时候，可以使用DP table记录已求可能解，避免可能解重复计算。 $f (19) = f (18) + f (17)$ 自底向上递推可以不用多次求 $f (18)$

DP三要素：1.状态转移：如何从大变小（由小的信息 + 有效判断条件）得出大的结论、2.边界条件、3.dp数组的定义和填充

典型题目：数组-子序列(连续/不连续)、字符串-子序列(不连续)，子串(连续)

Tips：

最优子问题应理解为对所有子问题的解求最值。要保证原问题的解必须包含在所有子问题中。各个班最高成绩可以推全校最高成绩；各个班最大成绩差不能推全校最大成绩差(最大成绩差可会出现在不同的班级)
状态转移方程是在穷举，DP table 是在聪明的穷举
子问题相互独立理解：每个科目考最高分，如果每个科目的成绩不相互独立，那其实每个科目都各自求一个最高分，最后无法由各个科目最高分得出总分，因为该状态不可达。
一维dp，dp[i] --以item[i]结尾的，有效的，最长XXX的长度

1. DP-Base: 重复子问题、状态转移

509.斐波那契数

509.斐波那契-带你了解重叠子问题, 其没有求最值，严格来说不是动态规划
509.斐波那契 -（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： $F (0) = 0 ， F (1) = 1$ ， $F (n) = F (n - 1) + F (n - 2) ，其中 n > 1$ 。给定 n ，请计算 F(n) 。

自顶向下(递归返回)、自低向上(循环迭代)、空间约简(只记录前两个状态)

class Solution {
    vector<int> _memo;
public:
	// 509. 斐波那契数  -- 重复子问题 f(20) = f(19) + f(18) ,  f(19)拆解又需要重新解f(18), 用memo/dp数组来记住字问题的解，需要求解一个子问题时，先去看看适否以及有人解过了。
	// - 自低向上(循环迭代) + 空间约简(只记录前两个状态)
    int fib(int n) {
        if (n < 2) {
            return n;
        }
        int fi_1 = 1;
        int fi_2 = 0;
        int res = 0;
        for (int i = 2; i < n+1; i++) {
            res = fi_1 + fi_2;
            fi_2 = fi_1;
            fi_1 = res;
        }
        return res;
    }
	// 自低向上(循环迭代) + DP tabel
    int fib_2(int n) {
        _memo.resize(n+1);
        if (n < 1) {
            return n;
        }
        _memo[1] = 1;
        for (int i = 2; i < n+1; i++) {
            _memo[i] = _memo[i-1] + _memo[i-2];
        }
        return _memo[n];
    }
    // 自顶向下(递归返回) + DP tabel
    int fib_1(int n) {
        _memo.resize(n+1);
        return helper_1(n);
    }
    int helper_1(int k) {
        if (k <= 1) {
            return k;
        }
        if (_memo[k] != 0) {
            return _memo[k];
        }
        _memo[k] = helper(k-1) + helper(k-2);
        return _memo[k];
    }
   // 自顶向下(递归返回) + 暴力穷举，子问题重复计算
   int fib_0(int n) {
        return helper(n);
    }
    int helper_0(int n) {
        if (n < 2) {
            return n;
        }
        return helper(n-1) + helper(n-2);
    }
};

322.零钱兑换

322.零钱兑换 – 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

class Solution {
public:
	//322. 零钱兑换 -- 状态转移-暴力递归(自顶向下)， for循环（自底向上） 
	//k=1, 2, 5 求amount=11, 可拆解为三个子问题取min, min(a=10, a=9,  a=6), 这三个方案+1硬币都能变成原文题的一个方案 （最优子结构 <- 子问题独立 <-硬币数量没有限制）
	// dp(n) 凑出amount为n的最少硬币数
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);   // dp[i] amount = i 需要的最少硬币数， 很烦
        dp[0] = 0;  // base case 总是很头疼的。
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i - coin] != amount+1) {
                    dp[i] = min(dp[i], dp[i-coin]+1);
                }
            }
        }
        return dp[amount] != amount+1 ? dp[amount]: -1;
    }
};

暴力解法：时间超出限制 - 39 / 189 个通过的测试用例

class Solution {
    int _res = -1;
    int _count = 0;
    long long _sum = 0;
public:
    int coinChange(vector<int>& coins, int amount) {
        dfs(coins, amount, 0);
        return _res;
    }

    void dfs(vector<int>& coins, int amount, int start) {
        if (_sum > amount) {
            return;
        }
        if (_sum == amount) {
            if (_res == -1) {
                _res = _count;
            } else {
                _res = min(_res, _count);
            }
            return;
        }

        for (int i = start; i < coins.size(); i++) {
            _sum += coins[i];
            _count++;
            dfs(coins, amount, i);
            _sum -= coins[i];
            _count--;
        }

    }
};

279.完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [i for i in range(n+1)]
        dp[0] = 0
        auxi_lsit = [i**2 for i in range(1, int(math.sqrt(n))+1)] # [1, 4, 9]
        for i in range(2, n+1):
            for val in auxi_lsit:
                if i - val >= 0:
                    dp[i] = min(dp[i], dp[i-val] + 1)
        return dp[n]

2. DP-Advanced 一维 - DP数组初值设置

300. 递增子序列最大长度 - DP

300.最长递增子序 - [longest-increasing-subsequence] 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

class Solution {
public:
      // 数组无序，nums[i] = 8, 可以接在nums[i-1] = 2后，也能接在nums[i-2] = 6 后面，明显 nums[i-2] = 6 能够构成的递增子序列潜力大一些，因为无序，所以我们要遍历一下 nums[i] 前面的所有潜在候选对象。
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int res = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {  // nume[i]接 在每个现成的递增子序列后，从有望构成新递增子序列里，找出最大的
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

53. 最大和子数组 - DP

53.最大子数组和 - 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

dp[i] = max(nums[i], nums[i] + dp[i-1]), nums[i]

自成一派：说明nums[i] > nums[i] + dp[i-1] , 即 dp[i-1] < 0, nums[i-1]成份被舍弃了，这些成分只有副作用，不要也罢，nums[i]开启新征程，往下去找一找
建立连结：说明nums[i] < nums[i] + dp[i-1], 即nums[i]<0,
如果nums[i]不太小(nums[i] + dp[i-1]>0), 还是有希望numi[i+1]能够打平numi[i]带来的副作用，
如果nums[i] 太小了(nums[i] + dp[i-1]>0), 在nume[i+1] 决策时，会直接把numi[i]成分舍弃。

// 动态规划数组的定义: dp[i] 最大和， 这个子数组是以 nums[i] 结尾的，dp[i] 只与 dp[i-1] 有关
// 状态转移方程: dp[i] = max(nums[i], nums[i] + dp[i-1])
// key1: 用 nums[i] 更新 dp[i] 时，nums[i] 可以成为已有数组的尾部，也可以成为单元素数组，这两种情况 nums[i] 都是作为子数组的结尾
// key2: 如果某一块数组的和为负数，这一块不会作为和最大连续子数组的结尾(多元素数组/单元素数组)，因为去掉这个部分，后半段加和会更大。  空间约减，将空间复杂度降为o(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int pre_max = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; i++) {
            int cur_max = max(pre_max + nums[i], nums[i]); // 大的会使下一段变得更大 
                                                          // 如果没有选pre_max + nums[i], 说明pre_max<0, 直接丢弃吧
            res = max(res, cur_max);
            pre_max = cur_max;

        }
        return res;
    }
};

# python 暴力解法 -> 一维dp -> 空间约简Dp 
class Solution:
    def maxSubArray0(self, nums: List[int]) -> int:
    """
    @note 暴力法-遍历(n-1)*n/2个子数组，找出最大和
          求和次数减少：用空间换时间，已经算过的和可以用二维数组存起来，如下
    """
       n = len(nums)
       dp = [[0] * n for _ in range(n)]

       res = nums[0]     # len(nums) >= 1 的假设
       for i in range(n):
           sub_arr_sum[i][i] = nums[i]
           res = max(res, nums[i])
       
       for i in range(n-2, -1, -1):
           for j in range(i+1, n):
               sub_arr_sum[i][j] = sub_arr_sum[i][j-1] + nums[j]
               res = max(res, sub_arr_sum[i][j])
       return res

    def maxSubArray(self, nums: List[int]) -> int:
        """
        @note 一维 dp 
        # [-2, 1, -3, 4, -1, 2, 1]
        # i = 0, dp[0] = 0
        # i = 1, dp[1] = max(1, 1) = 1
        # i = 2, dp[2] = max(-3, 1+-3) = -2 
        # i = 3, dp[3] = max(4, 4+-2) = 4
        # i = 4, dp[4] = max(-1, 4 -1) = 3
        # i = 5, dp[5] = max(2, 2 + 3) = 5
        """
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        res = dp[0]
        for i in range(1, n):
            dp[i] = max(nums[i], nums[i] + dp[i-1])
            res = max(res, dp[i])
        return res

    def maxSubArray2(self, nums: List[int]) -> int:
    	"""
		@note	 空间约减后，空间复杂度为0(1)
			dp 非负数 最大子数组和，如果为0，说明nums[i+1]更新dp数组时会重新开辟一个新的子数组
    	"""
        res = float("-INF")
        dp = 0
        for val in nums:
            dp += val        # [-1] 先加，更新答案，确定是否归零
            res = max(dp, res)
            dp = max(dp, 0)
        return res

152. 最大积子数组 - DP, 需要考虑dp_min

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

直接思路： $f (i)$ 表示以第i个元素结尾的乘积最大的子数组的积，状态转移方程为
$f(i)=\max\{f(i-1)* nums[i], nums[i]\}$
即， $f (i)$ 可以是 nums[i]加入前一段 $f_{max}(i-1)$ 贡献力量，或者 nums[i]自成一段，这两种情况取最大值。遍历所有的 $f (i)$ ，取一个最大的作为结果。

核心问题：当前位置的最优解不一定是由前一个位置的最优解得到。因为存在负数

如果num[i]是负数的话，我们希望以num[i-1]为结尾的某一个段的积也是一个负数，负负可以为正。

如果num[i-1]为正，我们希望以num[i-1]为结尾的某一个段的积也是一个正数，正的越多，乘积完越大。

所以再维护一个 $f_{min}(i)$ 表示以第i个元素结尾的乘积最小的子数组的积：
$f_{max}(i)=\max\{f_{max}(i-1)*a_i,f_{min}(i-1)*a_i,a_i\}\\ f_{min}(i)=\min\{f_{max}(i-1)*a_i,f_{min}(i-1)*a_i,a_i\}$

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // dp 和 贪心的界限在哪里？
        // 凡事只用到上一状态的都可以做空间约减
        int pre_max = nums[0];
        int pre_min = nums[0];
        int n = nums.size();
        int res = pre_max;
        for (int i = 1; i < n; i++) {
            int cur_max = max({nums[i], pre_max*nums[i], pre_min*nums[i]});   // 前面有可能产生0的结果
            int cur_min = min({nums[i], pre_max*nums[i], pre_min*nums[i]});
            res = max(res, cur_max);
            pre_max = cur_max;
            pre_min = cur_min;
        }
        return res;
        
    }
};

3. DP-Advanced 二维 - DP数组初值设置

931. 下降路径最小和 - 数

931.下降路径最小和 – 给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

class Solution {
public:
  	// 迭代求解，自底向上
    int minFallingPathSum(vector<vector<int>>& matrix) {
       int n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        copy(matrix[0].begin(), matrix[0].end(), dp[0].begin());  // base case
        for (int i = 1; i < n; i++) {
            for (int j = 0 ; j < n; j++) {
                int min_pre = 10001;  // 单元 100 * 行数100 累计最大值
                int offsets[3][2] = {{-1, -1,}, {-1, 0}, {-1, 1}};
                for (auto& offset:offsets) {
                    int pre_i = i + offset[0], pre_j = j + offset[1];
                    if (pre_i < 0 || pre_i >= n || pre_j < 0 || pre_j >= n) {
                        continue;
                    }
                    min_pre = min(min_pre, dp[pre_i][pre_j]);
                 }
                dp[i][j] = min_pre + matrix[i][j];  // 前路最短 + 走到[i][j]的增量
                // cout  << "i: " << i << ", j: "  << j << ", dp: " << dp[i][j] << endl;
            }
        }
        int res = 10001;
        for (int j = 0; j < n; j++) {
            res = min(res, dp[n-1][j]);
        }
        return res;
      
        // int res = 10001;
        // for (int j = 0; j < _n; j++) {
        //     res = min(res, helper(_m-1, j, matrix));
        // }
        // return res;
    }
		// 递归求解 自顶向下
    int helper(int row, int col, vector<vector<int>>& matrix) {
        // cout << row << ", " << col << endl;
        if (row < 0 || col < 0 || row > _m - 1 || col > _n -1 ) {
            // cout << "a: "<< row << ", " << col << endl;
            return 10001;    // 取不到的位置，返回无法娶到的值
        }
        if (row == 0) {
            // cout << "b: "<< row << ", " << col << endl;
            return matrix[row][col];
        }
        int tmp = 10001;
        int offsets[3][2] = {{-1, -1}, {-1, 0}, {-1, 1}};
        for (auto& offset : offsets) {
            int pre_row = row + offset[0];
            int pre_col = col + offset[1];
            tmp = min(tmp, helper(pre_row, pre_col, matrix) + matrix[row][col]);
            // cout << "c: "<< row << ", " << col << "," << tmp << endl;
        }
        return tmp;
    }
};

1143. 最长公共子序列 - 长度

1143.最长公共子序列 – 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

(两个字符串，二维dp 才是标配嘛)
dp[i][j] 表示s1[0]-s1[i] 于s2[0]-s2[j] 的最长公共子序序列，更新形式于512题类似，只不过初值和方向不大一样，初值为第0行第0列均为0，方向由上到下，由左到右。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // dp[i][j] t1[0-i] t2[0-j] 公共子序列的长度；
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (text1[i-1] == text2[j-1]) {  // 对角线传输，s_1[i-1] s_2[j-1]同为公共子序列一部分
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {                         // 边传输，s_1[i-1] s_2[j-1]其一 or none 为公共子序列的一部分
                                                 // dp[i-1][j] dp[i][j-1] 其一是通过对角线操作来的话，那么s_1[i-1] s_2[j-1] 其一是公共子序列的一部分
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

// 最长公共子序 - 回溯法去找是谁

def longestCommonSubsequence(self, text1, text2):
    l1, l2 = len(text1), len(text2)
    dp = [[0] * (l2 + 1) for _ in range(l1 + 1)]
    for i in range(1, l1 + 1):
        for j in range(1, l2 + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # return dp[-1][-1]
    #  回溯 只有加
    res_str=[""]*dp[-1][-1]
    i,j=l1,l2
    while(i>0):
        if dp[i][j]>dp[i-1][j]:                   # 比上面的大，不是来上面
            if dp[i][j]>dp[i][j-1]:				  # 	比左边的大，不是来自左边
                res_str[dp[i][j]-1]=text1[i-1]    # 		来自对角线操作
            else:                                 # 	没有左边大，来自左边 横坐标操作
                i+=1							  # 		i 需要先+1，最后的-1会抵消
            j-=1								  # 	没有左边大，来自左边，纵坐标操作
        i-=1
    print(res_str)

516. 最长回文子序列–(子序列不连续)长度

和上题的基本思路一样，不过dp数组表示的含义变为
dp[i][j] 表示s[i]-s[j]子串中回文序列的长度

# if s[i]==s[j]：dp[i][j] = dp[i+1][j-i]+2，
# if s[i]!=s[j]：dp[i][j] = max(dp[i+1][j],dp[i][j-1])
def longestPalindromeSubseq(self, s):
    n = len(s)
    if n < 2:
        return n
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for i in range(n-2, -1, -1):
        for j in range(i+1,n):
            if s[j] == s[i]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

221. 最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        // 有点像岛屿的数量，但是如何确定是正方形呢 - 不太一样
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        int res = 0;
        for (int i = 0 ; i < n; i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            res = max(res, dp[i][0]);
        }
        for (int j = 0; j < m; j++) {
            dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
            res = max(res, dp[0][j]);
        }

        for (int i = 1; i < n; i++) {

            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                }
                res = max(res, dp[i][j]);

            }

        }
        return res * res;
    }
};

4. 整数拆分、剪绳子、砍竹子 - 一维度dp

343. 整数拆分

给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积。
2 <= n <= 58

4.剑指 Offer 14- I. 剪绳子为k个整数段，使各个段成绩最大

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

LCR 131. 砍竹子 I

现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。
2 <= bamboo_len <= 58

LCR 132. 砍竹子 II

段长度均为正整数。请返回每段竹子长度的最大乘积是多少。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
2 <= bamboo_len <= 1000

动态规划求解

dp[i]: 长度为i 绳子至少剪了一次的最长长度
$max(dp[j]*(i-j),j*(i-j),dp[i]),j\in[1,i-1]$
n^2复杂度的DP

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1, 1);
        for (int i = 2; i < n+1; i++) {
            for (int j = 2; j < i; j++) {
                int factor = max(dp[j], j);
                dp[i] = max(dp[i], factor * (i-j));
            }
        }
        return dp[n];
    }
};

数学推导求解

通过数学不等式推到，可以得到，当每段长度为3时乘积最大。所以尽可能分为三段，最后一段依据具体情况判断：

class Solution(object):
    def cuttingRope(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=3:
            return n-1
        s, mod = n //3, n % 3   
        if mod == 0:
            res = 3**s
        elif mod == 1:
            res = 3**(s-1)*4 
        else:
            res = 3**s*2
        return res%(10**9+7)