代码随想录刷题攻略---动态规划1

 例题1

一个机器人位于一个 m x n 网格的左上角。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。

问总共有多少条不同的路径？

 动规五部曲

1.确定dp数组以及下标的含义

dp[i][j] ：表示从（0，0）出发，到(i, j) 共有dp[i][j]条不同的路径。

2.确定dp数组递推式

因为机器人只能向下或者向右移动，故dp[i][j]是从左边 dp[i][j-1] 或者上边 dp[i-1][j] 的路径叠加而来

故  dp[i][j]=dp[i][j-1]+dp[i-1][j]

3.dp数组初始化

由于机器人只能向下或者向右移动，故 dp[i][0]和 dp[0][j] 都只有一种直走的可能，值都为1

4.确定遍历顺序

由递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1可知]，dp[i][j]都是从其上方和左方推导而来，那么从左到右、从上到下一层一层遍历就能保证每一步都有初值了。

5.手动写几个dp[i][j]推导验证一下

code

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

---

例题2

一个机器人位于一个 m x n 网格的左上角 .

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。

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

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

动规五部曲

1.确定dp数组以及下标的含义

dp[i][j] ：表示从（0，0）出发，到(i, j) 共有dp[i][j]条不同的路径。

2.确定dp数组递推式

因为机器人只能向下或者向右移动，故dp[i][j]是从左边 dp[i][j-1] 或者上边 dp[i-1][j] 的路径叠加而来

故  dp[i][j]=dp[i][j-1]+dp[i-1][j]

3.dp数组初始化

由于机器人只能向下或者向右移动，且有故障的地方及之后的路是走不到的，故 dp[i][0]和 dp[0][j] 的值都为1，若碰到了故障，之后的值都为0。

4.确定遍历顺序

由递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1可知]，dp[i][j]都是从其上方和左方推导而来，那么从左到右、从上到下一层一层遍历就能保证每一步都有初值了。但如果当前的obstacleGrid[i][j]有障碍，那么当前的dp[i][j]赋值为0.

5.手动写几个dp[i][j]推导验证一下

code

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

---

例题3

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

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

 动规五部曲

1.确定dp数组以及下标的含义

dp[i][j] ：表示从（0，0）出发，到(i, j) 共有dp[i][j]条不同的路径。

2.确定dp数组递推式

因为机器人只能向下或者向右移动，故dp[i][j]是从左边 dp[i][j-1] 或者上边 dp[i-1][j] 的路径叠加而来

故  dp[i][j]=dp[i][j-1]+dp[i-1][j]

3.dp数组初始化

由于机器人只能向下或者向右移动，且有故障的地方及之后的路是走不到的，故 dp[i][0]和 dp[0][j] 的值都为1，若碰到了故障，之后的值都为0。

4.确定遍历顺序

由递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1可知]，dp[i][j]都是从其上方和左方推导而来，那么从左到右、从上到下一层一层遍历就能保证每一步都有初值了。但如果当前的obstacleGrid[i][j]有障碍，那么当前的dp[i][j]赋值为0.

5.手动写几个dp[i][j]推导验证一下

code：

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

---

例题四

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

动规五部曲

1.确定dp数组以及下标的含义

dp[i]：由i个整数（从1~i）能构成的二叉搜索书树有dp[i]种。

2.确定dp数组递推式

单纯从dp[i]推出递推式较困难，没什么头绪。于是我们从i为1、2、3等较小的树情况进行推理。

易得，i=1/2/3时情况如下：

i=1:

i=2:

i=3：

可见，i=3且根节点为1或3时，子树结构与i=2时的整棵树结构相似；当根结点为2时，其左右子树结构又与i=1时的整棵树结构相似。

i=3且根节点为1/3时，二叉搜索树的数量分别为dp[2]的值；根节点为2时，二叉搜索树的数量为dp[1]的值，故dp[3]=dp[2]+dp[2]+dp[1]。当i的数字增加时，二叉树的情况会越来越复杂（可能有两层左子树和一层右子树），所以dp[3]的递推式可以看成是dp[3]=1*dp[2]+1*dp[2]+(1或dp[1])*dp[1]，i值增加时，系数1也会发生变化，但我们发现，这三个整式的本质是左子树的二叉树数量*右子树的二叉树数量 之和。

故我们推测dp[i]的递推式为 dp[i] += dp[i-j]*dp[j-1]，i-j的最大值为i-1，对应的情况是根节点的某一颗子树为空的情况。随着j增大，根节点的两个子树上的结点随之变化。

3.dp数组初始化

易推出 dp[0]=1,dp[1]=1

4.确定遍历顺序

由递推公式可知，dp[i]都是dp[i-j]推导而来的，那么在循环嵌套中先变换j再变换i就能保证dp[i]的来源了。

5.手动写几个dp[i][j]推导验证一下

code

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