目录

1.不同路径1.题目链接2.算法原理详解3.代码实现

2.不同路径 II1.题目链接2.算法原理详解3.代码实现

3.珠宝的最高价值1.题目链接2.算法原理详解3.代码实现

1.不同路径

1.题目链接

不同路径

2.算法原理详解

思路：

确定状态表示 -> <code>dp[i][j]的含义

走到dp[i][j]的时候，一共有多少种方式

推导状态转移方程

<code>dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

初始化：dp表多开一行和一列虚拟结点，避免处理边界

dp[0][1] = 1 || dp[1][0] = 1

确定填表顺序：从上往下，从左往右

确定返回值：<code>dp[n][m]

上述如果dp表不多开那一行和一列虚拟结点会怎么样？

需要做边界处理，将第一列和第一行先初始化为1

3.代码实现

int uniquePaths(int n, int m)

{

vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

dp[0][1] = 1;

for(int i = 1; i <= n; i++)

{

for(int j = 1; j <= m; j++)

{

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

}

}

return dp[n][m];

}

2.不同路径 II

1.题目链接

不同路径 II

2.算法原理详解

思路：

确定状态表示 -> dp[i][j]的含义

走到dp[i][j]的时候，一共有多少种方式

推导状态转移方程

<code>dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

初始化：<code>dp表多开一行和一列虚拟结点，避免处理边界

dp[0][1] = 1 || dp[1][0] = 1

确定填表顺序：从上往下，从左往右

确定返回值：<code>dp[n][m]

3.代码实现

int uniquePathsWithObstacles(vector<vector<int>>& ob)

{

int n = ob.size(), m = ob[0].size();

vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

dp[0][1] = 1;

for(int i = 1; i <= n; i++)

{

for(int j = 1; j <= m; j++)

{

if(ob[i - 1][j - 1] == 0) // 注意下表映射关系

{

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

}

}

}

return dp[n][m];

}

3.珠宝的最高价值

1.题目链接

珠宝的最高价值

2.算法原理详解

思路：

确定状态表示 -> dp[i][j]的含义

到达dp[i][j]的时候，此时的最大价值

推导状态转移方程

dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1]) + g[i][j]

初始化：<code>dp表多开一行和一列虚拟结点，避免处理边界

第一行和第一列全部初始化为0即可

确定填表顺序：从上往下，从左往右

确定返回值：dp[n][m]

3.代码实现

int jewelleryValue(vector<vector<int>>& frame)

{

int n = frame.size(), m = frame[0].size();

vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

for(int i = 1; i <= n; i++)

{

for(int j = 1; j <= m; j++)

{

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];

}

}

return dp[n][m];

}