动态电商网站怎么做,山东城市建设职业学院教务网网站,网站维护模板,工作邮箱怎么注册目录 1.不同路径1.题目链接2.算法原理详解3.代码实现 2.不同路径 II1.题目链接2.算法原理详解3.代码实现 3.珠宝的最高价值1.题目链接2.算法原理详解3.代码实现 1.不同路径
1.题目链接
不同路径 2.算法原理详解
思路#xff1a; 确定状态表示 - dp[i][j]的含义 走到dp[… 目录 1.不同路径1.题目链接2.算法原理详解3.代码实现 2.不同路径 II1.题目链接2.算法原理详解3.代码实现 3.珠宝的最高价值1.题目链接2.算法原理详解3.代码实现 1.不同路径
1.题目链接
不同路径 2.算法原理详解
思路 确定状态表示 - dp[i][j]的含义 走到dp[i][j]的时候一共有多少种方式 推导状态转移方程 dp[i][j] dp[i - 1][j] dp[i][j - 1] 初始化dp表多开一行和一列虚拟结点避免处理边界 dp[0][1] 1 || dp[1][0] 1 确定填表顺序从上往下从左往右 确定返回值dp[n][m] 上述如果dp表不多开那一行和一列虚拟结点会怎么样 需要做边界处理将第一列和第一行先初始化为1 3.代码实现
int uniquePaths(int n, int m)
{vectorvectorint dp(n 1, vectorint(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]的时候一共有多少种方式 推导状态转移方程 dp[i][j] dp[i - 1][j] dp[i][j - 1] 初始化dp表多开一行和一列虚拟结点避免处理边界 dp[0][1] 1 || dp[1][0] 1 确定填表顺序从上往下从左往右 确定返回值dp[n][m] 3.代码实现
int uniquePathsWithObstacles(vectorvectorint ob)
{int n ob.size(), m ob[0].size();vectorvectorint dp(n 1, vectorint(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] 初始化dp表多开一行和一列虚拟结点避免处理边界 第一行和第一列全部初始化为0即可 确定填表顺序从上往下从左往右 确定返回值dp[n][m] 3.代码实现
int jewelleryValue(vectorvectorint frame)
{int n frame.size(), m frame[0].size();vectorvectorint dp(n 1, vectorint(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];
}
