算法修炼-动态规划之路径问题（1）
思路：选定一个网格为终点，走到这个网格的所有走法就是这个网格的上面一个网格的所有走法加上这个网格左边一个网格的所有走法，然后做好初始化工作就行。
class Solution {
public:
int uniquePaths(int m, int n)
{
//dp表
int arr[m][n];
//特殊处理
if(m == 1 || n == 1)
return 1;
//初始化
for(int i = 0; i<m; i++)
{
arr[i][0] = 1;
}
for(int i = 0; i<n; i++)
{
arr[0][i] = 1;
}
//状态转移方程
for(int i = 1; i<m; i++)
{
for(int j = 1; j<n; j++)
{
arr[i][j] = arr[i][j-1] + arr[i-1][j];
}
}
return arr[m-1][n-1];
}
};
思路： 这道题可以看做事上面那道题的升级版，我的思路就是先将创建出来的dp表先全部初始化为0，在状态转移方程中，如果遇到障碍物，就保持dp表中障碍物位置的值仍为0，其余位置的值为它的上面加上它的左边。这时有人可能就会有疑问了，如果一个位置的左边或者是上面为障碍物不影响赋值吗？答案是不影响的。因为障碍物位置的值就是0，加上跟没加没有区别，所以可以统一加上。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
//dp表
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
//初始化
for(int i = 0; i<n; i++)
{
if(obstacleGrid[0][i] == 0)
dp[0][i] = 1;
else
break;
}
for(int i = 0; i<m; i++)
{
if(obstacleGrid[i][0] == 0)
dp[i][0] = 1;
else
break;
}
//状态转移方程
for(int i= 1; i<m; i++)
{
for(int j = 1; j<n; j++)
{
if(obstacleGrid[i][j] != 1)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];LCR 166. 珠宝的最高价值 - 力扣（LeetCode）
思路：这题采用的方法略微跟上面两题不同，这一题的dp表我多补了一行和一列，通过比较所在位置的上面一个位置和左边一个位置谁大，加上值大的那个位置，只不过这种方法要注意两个表之间下标的对应关系。
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame)
{
//dp表
int m = frame.size();
int n = frame[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1));
//初始化+状态转移方程
for(int i = 1; i<=m ;i++)
{
for(int j = 1; j<=n; j++)
{
if(dp[i-1][j] < dp[i][j-1])
{
dp[i][j] += frame[i-1][j-1]+dp[i][j-1];
}
else
{
dp[i][j] += frame[i-1][j-1] + dp[i-1][j];
}
}
}
return dp[m][n];
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读