62. 不同路径
题目链接：62. 不同路径
算法原理
状态表示：
dp[i,j]：以[i, j]位置为结尾，走到[i, j]位置有多少种方式状态转移方程：
根据最近的一步划分问题
只能从左侧和上侧到达该位置，所以两种情况
这里是一步，而不是一种方法，比如说
A->B->C->[i,j]，这是这个方法里面的一步，所以不加1所以
dp[i][j] = dp[i-1][j] + dp[i][j-1]初始化：
保证填表不越界，这里采用添加虚拟节点在虚拟节点当中
[0,1]位置填1，其他位置填0，即可按照我们的要求初始化完毕，因为是根据上和左的值相加
填表顺序：
大方向是从上往下填每一行，每一行从左往右返回值：
dp[m][n]
代码实现
class Solution {
public:
int uniquePaths(int m, int n)
{
vector<vector<int>> dp(m+1, vector<int>(n+1));
dp[0][1] = 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][n];
}
};
63. 不同路径 II
题目链接：63. 不同路径 II
这题就是上一题的升级版，加入了“障碍物”（该位置不能走）
算法原理
状态表示：
经验+题目要求：dp[i][j]表示到达[i,j]位置时，一共有多少只方法状态转移方程：
这里加入了判断是否有“障碍物的情况”
有障碍物的情况下，我们的
dp[i][j]里面填的值是0，所以放些加就好了初始化：
也是和上题类似，只不过这里的映射关系，需要注意一下，dp表里面要找到矩阵的对应位置，需要减1，即obstacleGrid[i-1][j-1]填表顺序： 也和上一题一样
返回值：
dp[m][n]
代码实现
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1));
dp[0][1] = 1;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
//映射关系需要减1
if(obstacleGrid[i-1][j-1] == 0)
{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m][n];
}
};
LCR 166. 珠宝的最高价值
题目链接：LCR 166. 珠宝的最高价值
题目意思就是从左上角到右下角能获取的最大值价值（每次只能向下或者向右走）
算法原理
- 状态表示：
经验+题目要求：dp[i][j]表示到达[i,j]位置时，此时能拿到的最大价值 - 状态转移方程：
根据最近的一步划分问题
- 初始化：
保证填表不越界，这里也是采用虚拟节点，这个虚拟节点的值不影响，都设置为0，因为“珠宝”的价值，全部都是大于0的，我们取的是max - 填表顺序： 从上到下填每行，每行从左往右
- 返回值：
dp[m][n]
代码实现
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame)
{
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++)
{
//注意下标的映射
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1];
}
}
return dp[m][n];
}
};