前言：

本篇我们主要刷动态规划的题，解题还是严格按照我们在【夜深人静写算法】栏目下的解题步骤，大家如果没学过动态规划的可以先看看我写的动态规划文章介绍。

【夜深人静学数据结构与算法 | 第十篇】动态规划_我是一盘牛肉的博客-CSDN博客

63. 不同路径 II - 力扣（LeetCode）

一个机器人位于一个 m * n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

其实这题跟我们在动态规划中讲解的例题答题思路基本一致，就是需要再加一个判断条件：
如果这块是障碍点，那么我们就将这个点的路径数设置为0，并且放弃这条路。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
	if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍，直接返回0
       { 
            return 0;
       }    
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)//obstacleGrid[i][0] == 0也就是没有障碍物
        {
            dp[i][0] = 1;
        } 
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++)// obstacleGrid[0][j] == 0也就是没有障碍物
        {
             dp[0][j] = 1;
        };

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1)
                {
                    continue;
                } 
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];

    }
};

343. 整数拆分 - 力扣（LeetCode）

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

其实这道题我们要明白：要想使得拆出来的整数乘积大，我们就要尽量的保证拆出来的整数接近。也就是尽可能拆出来相同的数。

关于为什么是这样的，我们需要用数学公式解决：

这个问题可以通过数学方法进行解释，思路如下：

假设将整数 n 拆分成 k 个正整数相加，这 k 个正整数分别为 a1, a2, ..., ak，则它们的乘积为：

P = a1 * a2 * ... * ak

我们可以对这个乘积进行求导，得到：

dP/da1 = a2 * a3 * ... * ak
dP/da2 = a1 * a3 * ... * ak
...
dP/da(k-1) = a1 * a2 * ... * a(k-1)
dP/da(k) = a1 * a2 * ... * a(k-1)

由于这k个正整数相加得到的和为n，因此有：

a1 + a2 + ... + ak = n

可以使用拉格朗日乘数法求解上面的一组方程，得到：

a1 = n / k
a2 = n / k
...
ak-1 = n / k
ak = n - (k-1) * n / k

可以看到，当 k 越大时，每个数都越趋近于相等，因此其乘积也会越来越大，直到取到最大值。

因此，我们可以通过枚举每个 k，来找到乘积最大的 k 和对应的乘积。

看不懂也没有关系，知道这个结论就可以了，但是如果更好的理解这个数学验证的话，我们就可以在验证的时候做更好的优化。

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

但其实本道题还可以用贪心算法的思路来做，但是贪心算法的代码虽然简洁，但是数学公式证明起来比较麻烦。

本题是可以用贪心算法进行求解的。

1. 当n>=5时，将n拆分成3和n-3的和，比将其拆分成2和n-2的和要优秀，即：

n-3 > n-2 && 3*(n-3) > 2*(n-2)

这个性质可以通过一系列代数计算证明。

2. 当n>=5时，将n拆分成3的个数不会小于将其拆分成2的个数，即：

n mod 3 <= 1

这个性质也可以通过一系列代数计算证明。

基于以上结论，可以采用贪心算法，将整数n尽可能地拆分成3的和，直到最后得到的整数小于5。如果最后得到的整数等于1，则将其与最后一个3合并为4。

这种贪心策略的正确性可以通过数学归纳法证明。这里只给出其中一个例子：

当n=6时，根据以上贪心策略，将其拆分成3和3的和，乘积为9。然而，将其拆分成2和2和2的和，乘积为8，不是最优解。但是，当n=5时，按照贪心策略，将其拆分成3和2的和，乘积为6；而将其拆分成2和3的和，乘积为5，不是最优解。又因为任何大于5的整数都可以通过一系列的拆分得到6和2或3的和，因此对于所有大于5的整数，采用贪心策略是最优的。

因此，可以使用贪心算法来解决这个问题。

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        int result = 1;
        while (n > 4) {
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
};