例题：不同路径2（带障碍）
题目描述：
dp数组的定义 ：
dp[i][j]的含义是：从（0，0）到（i，j）的不同路径
递推公式：
当路线中有了障碍，此路不通，所以在不同路径的递推公式上需要增加条件
if（obs[i,j]==0）没有障碍，dp[i][j]= dp[i-1][j]+dp[i][j-1]
if（obs[i][j]==1）有障碍，不进行推导
obs数组表示障碍
初始化dp数组
障碍的后面应该是0（原因：遇到障碍后，即使我们越过障碍，也无法再去障碍的后面，因为题目要求只能向右或向下，要想回到障碍后面则需要向左和向上，所以障碍的后面路径为0）
由此，考虑一种特殊情况：当障碍在起始位置、终止位置时路径为0
for（int i=0;i<m&&obs[i][0]==0;i++） dp[i][0]=1;
for(int j=0;j<n&&obs[0][j]==0;j++) dp[0][j]=1;
遍历顺序
从左到右，从上到下
相关代码
c++
class solution
{
public:
int uniquePathWithObstacles(vector <vector<int>>&obstacleGrid)
{
int m=obstacleGrid.size();
int n=obstacleGrid.size();
if(obstacleGrid[m-1][n-1]==1||obstacleGrid[0][0]==1) return 0;
//在起点、终点及它们的前面出现障碍，无法到达
vector<vector<int>> dp(m,vector<int>(n,0));
for(int i=0;i<m&&obstacleGrid[i][0]==0;i++) dp[i][0]=1;
{
for(int j=0;j<n&&obstacleGrid[0][j]==0;j++) dp[0][j]=1;
{
if (obstacleGrid[i][j]=1) continue;
dp[i][j]=dp[i-1][j]+[dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}时间复杂度：O(m×n)
空间复杂度：O(m×n)
空间优化代码
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid[0][0] == 1)
return 0;
vector<int> dp(obstacleGrid[0].size());
for (int j = 0; j < dp.size(); ++j)
if (obstacleGrid[0][j] == 1)
dp[j] = 0;
else if (j == 0)
dp[j] = 1;
else
dp[j] = dp[j-1];
for (int i = 1; i < obstacleGrid.size(); ++i)
for (int j = 0; j < dp.size(); ++j){
if (obstacleGrid[i][j] == 1)
dp[j] = 0;
else if (j != 0)
dp[j] = dp[j] + dp[j-1];
}
return dp.back();
}
};时间复杂度：O(m×n)
空间复杂度：O(m)
例题：整数拆分
题目描述：
题目理解：
2 = 1+1 1×1=1
10=3+3+4 3×3×4=36
思考： 让每个拆分后的数近似相等
如何拆分？
10=2+8 -->8=2+6 -->6=2+4 (递推的思路，有了递推的思路之后，就可以思考可以使用动态规划）
dp数组的定义 ：
dp[i]代表第i个数的乘积最大化
对i个数进行拆分，得到的最大乘积为dp[i]
递推公式：
i:
两个数：jx(j-i)
三个数及三个数以上：jxdp[i-j]
问题：为什么只拆i，不拆j
固定了j，其余的式子只要拆i-j原因：只要其他的拆分式子中包含j，则相当于j的拆分
问题：式子是否改为dp[j]xdp[i-j]更合理？
这里默认了i会被拆分为4个数
初始化dp数组
dp[0]=0 dp[1]=0 dp[2]=1（前面两种是没有意义的，从2开始有意义）
遍历顺序
for(i=3;i<=n;i++)
for(j=1;j<i;j++)
dp[i]=max(j×(i-j),jxdp[i-j],dp[i])
尝试不同的j值进行拆分，根据上面的两种情况取最大，当换下一个j的时候，就和当前的dp[i]比较，相当于取不同j下面的最大值
相关代码
动规代码：
class solutin
{
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;j++)
dp[i]=(dp[i],max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}时间复杂度：O(n^2)
空间复杂度：O(n) 文章来源：https://www.toymoban.com/news/detail-848274.html
贪心代码：
初始化逻辑有问题文章来源地址https://www.toymoban.com/news/detail-848274.html
class Solution {
public:
int integerBreak(int n) {
if (n <= 3) return 1 * (n - 1);
vector<int> dp(n + 1, 0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for (int i = 4; i <= n ; i++) {
for (int j = 1; j <= i / 2; j++) {
dp[i] = max(dp[i], dp[i - j] * dp[j]);
}
}
return dp[n];
}
};
例题：二叉搜索树
到了这里，关于动态规划例题（代码随想录学习）——持续更新的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
