文章目录KEY1语法1 如何初始化有变量的数组2 三个数求最大值2想清楚问题建模了解二叉搜索树性质62.不同路径整个代码63. 不同路径 II (即有障碍版)整个代码343.整数拆分(1)最关键的是思路、问题建模(2) 需要注意的细节整个代码96.不同的二叉搜索树思路整个代码KEY1语法1 如何初始化有变量的数组intfunction(intn){vectorinta(n,0);注意不能用int dp[n1]{0};会报错2 三个数求最大值用{}把三个需要比较的数包起来再传入max()dp[i]max({a,b,c});2想清楚问题建模了解二叉搜索树性质二叉搜索树的性质头节点左边的所有节点都小于他右边的都大于他而且左右子树也是二叉搜索树有n个不同值节点的二叉搜索树不管节点值具体是多少只要是不同的值树的所有可能的结构是固定的62.不同路径没啥算法课学过想清楚即可。整个代码classSolution{public:intuniquePaths(intm,intn){intdp[m][n];for(inti0;im;i){dp[i][0]1;}for(intj0;jn;j){dp[0][j]1;}for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m-1][n-1];}};63. 不同路径 II (即有障碍版)把思路理清楚就可以整个代码class Solution{public:intuniquePathsWithObstacles(vectorvectorintobstacleGrid){// 注意如何获得二维数组的长度intmobstacleGrid.size();intnobstacleGrid[0].size();intdp[m][n];// 初始化if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1)return0;dp[0][0]1;for(inti1;im;i){if(obstacleGrid[i][0]0)dp[i][0]dp[i-1][0];elsedp[i][0]0;}// if (m1)for(intj1;jn;j){if(obstacleGrid[0][j]0)dp[0][j]dp[0][j-1];elsedp[0][j]0;}// 开始计算整个棋盘for(inti1;im;i){for(intj1;jn;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. 把 n6 拆成 k 个数可以拆成2个数也可以3个4个。。。怎么建模动态优化需要嵌套的问题如何嵌套先定义 dp[i] 是把 i 拆开之后相乘能得到的最大结果尝试先看看拆成2个数的情况i6j 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){vectorintdp(n1,0);// 初始化dpdp[0]0;dp[1]0;dp[2]1;for(inti3;in;i){for(intj1;ji/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个点根结点为3123456712在左子树4567在右子树左右子树也都为二叉搜索树而左右子树的节点数确定后左右子树的排列方式数量也确定了⇒ 可以由左右子树各自的数量得到该点作为 root 时排列组合数量即相乘。整个代码class Solution{public:intnumTrees(intn){vectorintdp(n1,0);dp[0]1;dp[1]1;// dp[2]2;for(inti2;in;i){for(intj1;ji;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不同路径 IIhttps://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html视频讲解https://www.bilibili.com/video/BV1Ld4y1k7c6整数拆分 可跳过本题思路并不容易想一刷建议可以跳过。如果学有余力可以看视频理解一波。https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html视频讲解https://www.bilibili.com/video/BV1Mg411q7YJ96…不同的二叉搜索树 可跳过本题思路并不容易想一刷建议可以跳过。 如果学有余力可以看视频理解一波。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
