【Day29 LeetCode】动态规划DP

首先是dp数组，dp[i][j]表示从起点(0, 0)到达当前位置(i, j)的路径数，转移方程从只能向下和向右移动可知，初始化边界可直观推出第一行和第一列上的位置只有一条路径。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        // 初始化
        for(int i=0; i<m; ++i)
            dp[i][0] = 1;
        for(int i=0; i<n; ++i)
            dp[0][i] = 1;
        // 循环
        for(int i=1; i<m; ++i)
            for(int j=1; j<n; ++j)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        return dp[m-1][n-1];
    }
};

空间复杂度优化，采用一维数组来记录一行的状态，通过循环来更新dp[i-1][j]的值。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        for(int i=1; i<m; ++i)
            for(int j=1; j<n; ++j)
                dp[j] += dp[j-1];
        return dp[n-1];
    }
};

这题相比于上一次只是多了障碍物的情况，遇到障碍物则路径为0。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        // 初始化
        for(int i=0; i<m; ++i){
            if(obstacleGrid[i][0]==0)
                dp[i][0] = 1;
            else
                break;
        }
        for(int i=0; i<n; ++i){
            if(obstacleGrid[0][i]==0)
                dp[0][i] = 1;
            else
                break;
        }
        // 循环
        for(int i=1; i<m; ++i)
            for(int j=1; j<n; ++j)
                dp[i][j] = (obstacleGrid[i][j]==0? dp[i-1][j] + dp[i][j-1] : 0);
        return dp[m-1][n-1];
    }
};

同样的空间复杂度优化

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<int> dp(n+1);
        dp[1] = (obstacleGrid[0][0]==0);
        for(int i=0; i<m; ++i)
            for(int j=0; j<n; ++j)
                dp[j+1] = (obstacleGrid[i][j]==1 ? 0 : (dp[j]+dp[j+1]));
        return dp[n];
    }
};

首先建立dp数组，dp[i]表示正整数i+1的整数拆分的最大乘积，dp[i]可由dp[0]*dp[i-1],dp[1]*dp[i-2],…,dp[i/2]*dp[i-i/2-1]取最大值（进行情况），i+1至少被分成两个整数。但这么做结果会都是1。除了1不可再拆分，其他数在进行比较的时候就已经进行了拆分，dp[i-1]如果是表示已经拆分后的最大乘积，可能拆分后的乘积没有不拆分的大，那么在求dp[i]的时候，由于比较的时候i至少已经被分成两个整数，比较的dp[0]*dp[i-1]可能不是当前索引的最大值，所以，除了最后的结果外，其它数字需要将拆分后的结果与不拆分的结果进行比较取最大。
需要重新理解dp方程，dp[i]除了最后一个数外，表示的是 拆分后的整数最大乘积和自身不拆分的值取最大值。
代码如下：

class Solution {
public:
    int integerBreak(int n) {
        // dp[i]表示正整数 i+1 的整数拆分的最大乘积
        vector<int> dp(n, 1);
        for(int i=1; i<n; ++i){
            dp[i-1] = max(dp[i-1], i); // 对前一个数进行拆分和不拆分的情况取最大
            for(int j=0; j<(i+1)/2; ++j)
                dp[i] = max(dp[i], dp[j]*dp[i-j-1]);
        }
        return dp[n-1];
    }
};

这题dp方程由于涉及到二叉搜索树不是很好想。假设以i为二叉搜索树的根节点，那么此二叉搜索树有i-1个节点的左子树和n-i个节点的右子树，这些都可以通过dp方程来记录。
所以，dp数组dp[i]表示节点数为i的二叉搜索树的种数，然后遍历以1~i为根节点的二叉搜索树的种数。所以得出以下代码：

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=i; ++j)
                dp[i] += dp[j-1] * dp[i-j];
        return dp[n];
    }
};