【代码随想录算法训练营第33天】动态规划part02 |62.不同路径 | 343.整数拆分 | 96.不同的二叉搜索树

KEY

（1）语法

1> 如何初始化有变量的数组：

intfunction(intn){vector<int>a(n,0);

注意，不能用int dp[n+1]={0};会报错

2> 三个数求最大值

用{}把三个需要比较的数包起来再传入max()

dp[i]=max({a,b,c});

（2）想清楚问题建模

了解二叉搜索树性质：

二叉搜索树的性质：头节点左边的所有节点都小于他，右边的都大于他；而且左右子树也是二叉搜索树
有n个不同值节点的二叉搜索树，不管节点值具体是多少，只要是不同的值，树的所有可能的结构是固定的

62.不同路径

没啥，算法课学过，想清楚即可。

整个代码：

classSolution{public:intuniquePaths(intm,intn){intdp[m][n];for(inti=0;i<m;i++){dp[i][0]=1;}for(intj=0;j<n;j++){dp[0][j]=1;}for(inti=1;i<m;i++){for(intj=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}returndp[m-1][n-1];}};

63. 不同路径 II (即有障碍版)

把思路理清楚就可以：

整个代码：

class Solution{public:intuniquePathsWithObstacles(vector<vector<int>>&obstacleGrid){// 注意：如何获得二维数组的长度intm=obstacleGrid.size();intn=obstacleGrid[0].size();intdp[m][n];// 初始化if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1)return0;dp[0][0]=1;for(inti=1;i<m;i++){if(obstacleGrid[i][0]==0)dp[i][0]=dp[i-1][0];elsedp[i][0]=0;}// if (m==1)for(intj=1;j<n;j++){if(obstacleGrid[0][j]==0)dp[0][j]=dp[0][j-1];elsedp[0][j]=0;}// 开始计算整个棋盘for(inti=1;i<m;i++){for(intj=1;j<n;j++){dp[i][j]=0;if(obstacleGrid[i-1][j]==0)dp[i][j]+=dp[i-1][j];if(obstacleGrid[i][j-1]==0)dp[i][j]+=dp[i][j-1];if(obstacleGrid[i][j]==1)dp[i][j]=0;}}returndp[m-1][n-1];}};

343.整数拆分

(1)💡最关键的是思路、问题建模：

思考：eg. 把 n=6 拆成 k 个数，可以拆成2个数，也可以3个，4个。。。怎么建模？
动态优化需要嵌套的问题，如何嵌套？
先定义 dp[i] 是把 i 拆开之后相乘能得到的最大结果
💡尝试：先看看拆成2个数的情况

i=6j i-j1523324251

即dp[i] = j * (i - j)(拆成2个时，即 k = 2时)
💡如何扩展到拆成更多数的情况？
==> 因为前面 j 已经遍历所有可能情况了，所以就只需要把后面的 （i - j）也拆开，用他拆开相乘能得到的最大结果去乘上 j
即：dp[i] = j * dp[i - j](k >= 3)
就得到了递推公式。

然后初始化 dp 数组：

dp[0]=0dp[1]=0dp[2]=1

(2) 需要注意的细节

不仅仅是dp[i] = max(j * (i - j), j * dp[i - j])，注意此时还在j循环里，所以此时对比出来的只是对于现在这个j得到的最大值，而我们需要对现在这个i得到的最大值，所以再加上一个比较：和现在的dp[i]比大小，这样才能得到对现在这个i的最大值，所以对比公式写为：

dp[i]=max({j*(i-j),j*dp[i-j],dp[i]});

其中，注意一个语法问题：用{}把三个需要比较的数包起来再传入max()

整个代码：

class Solution{public:intintegerBreak(intn){vector<int>dp(n+1,0);// 初始化dpdp[0]=0;dp[1]=0;dp[2]=1;for(inti=3;i<=n;i++){for(intj=1;j<=i/2;j++){dp[i]=max({j*(i-j),j*dp[i-j],dp[i]});// 需要和dp[i]对比，因为在这一行算出来的其实是某个j的时候的最大值，而我们需要遍历这个i的所有j之后的最大值，所以需要和现在这个i的最大值对比取最大}}returndp[n];}};

96.不同的二叉搜索树

思路：

二叉搜索树的性质：头节点左边的所有节点都小于他，右边的都大于他；而且左右子树也是二叉搜索树
有n个不同值节点的二叉搜索树，不管节点值具体是多少，只要是不同的值，树的所有可能的结构是固定的
⇒ 定下来根节点是几号节点后，他左边右边的子树各有几个点也是确定的了
eg. 总共7个点，根结点为3

1234567

1，2在左子树，4，5，6，7在右子树
左右子树也都为二叉搜索树

而左右子树的节点数确定后，左右子树的排列方式数量也确定了
⇒ 可以由左右子树各自的数量得到该点作为 root 时排列组合数量，即相乘。

整个代码：

class Solution{public:intnumTrees(intn){vector<int>dp(n+1,0);dp[0]=1;dp[1]=1;// dp[2]=2;for(inti=2;i<=n;i++){for(intj=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j];}}returndp[n];}};

第九章 动态规划part02

今天开始逐渐有 dp的感觉了，前 两题 不同路径，可以好好研究一下，适合进阶

详细布置

62.不同路径

本题大家掌握动态规划的方法就可以。 数论方法 有点非主流，很难想到。

https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
视频讲解：https://www.bilibili.com/video/BV1ve4y1x7Eu

63. 不同路径 II

https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html
视频讲解：https://www.bilibili.com/video/BV1Ld4y1k7c6

343. 整数拆分 （可跳过）
     本题思路并不容易想，一刷建议可以跳过。如果学有余力，可以看视频理解一波。

https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
视频讲解：https://www.bilibili.com/video/BV1Mg411q7YJ

96…不同的二叉搜索树 （可跳过）
本题思路并不容易想，一刷建议可以跳过。 如果学有余力，可以看视频理解一波。

https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1eK411o7QA