62 leetcode 不同路径---动态规划
在这里插入图片描述
在这里插入图片描述
动态规划解题三大步骤
- 动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤
- 第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
- 第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]……dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。
- 第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。
下面讲解不同路径这道题：
- 1.数组元素含义：到达当前点的不同路径总和
- 2.数组元素之间的关系式：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]
- 3.找出初始值：第一行和第一列所有值都为1，因为只能往右或者往下走
class Solution {
public:
int uniquePaths(int m, int n)
{
vector<vector<int>> dp(m,vector<int>(n));
for (int i = 0; i < m; i++)
dp[i][0] = 1;
for (int i = 0; i < n; i++)
dp[0][i] = 1;
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
在这里插入图片描述
递归解法
- 1.结束条件:到达终点，或者到达边界
- 2.本级递归做什么：朝着下方和右方不断探索，并且记录起点到达每一个点的不同路径可走总数
- 3.返回值：返回解法数
- 要记录当前走的位置和当前位置走法的总数，这里用unordered_map容器来记录
- 递归算法可以理解为先不断探索到（m-1,n-1）位置然后从该位置进行回溯，相当于从(m-1,n-1)位置当做起点，计算到(0,0)点的全部走法数
- 注意： 这里要舍去重复计算某一点的走法总数，不然递归会超时
在这里插入图片描述
class Solution {
public:
int uniquePaths(int m, int n)
{
map<pair<int,int>, int> path;
return backFind(path,0,0,m,n);
}
int backFind(map<pair<int, int>,int>& path,int i,int j,int m,int n )
{
//判断当前点的走法数是否已经被计算过
if (path.count({i,j})==1)
{
return path[{i, j}];//返回当前位置对应的走法总数
}
//结束条件：遇到边界或者到达目标点
if (i == m - 1 || j == n - 1)
{
return 1; //注意：回溯过程可以看做从把(m-1,n-1)当做起点计算到(0,0)点的走法总数
}
int right = backFind(path,i+ 1, j, m, n);
int left = backFind(path,i, j+1, m, n);
path[{i, j}] = right + left;//当前i,j位置对应的走法总数
return right + left;
}
};
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/04/29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
