1. 斐波那契数(LeetCode509)
题目描述:https://leetcode.cn/problems/fibonacci-number/description/
解法1:动态规划(基础版)
解题思路:动态规划五部曲
- Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]:第i个数的斐波那契数值是dp[i]
- Step2:确定递推公式 - dp[i] = dp[i - 1] + dp[i - 2] 题目已给
- Step3:初始化dp数组 - 由递推公式可知,需要初始化前两个元素(题目已给) - dp[0] = 0- dp[1] = 1
- Step4:确定遍历顺序 - 由递推公式可知,后面的斐波那契数值依赖于前面两个- 因此,需要从前向后遍历
- Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int fib(int n)
{
if (n <= 1) return n;
// Step3:初始化dp数组
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
// Step4:确定遍历顺序
for (int i = 2; i <= n; i++)
{
// Step2:确定递推公式
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
int main()
{
int n = 4;
Solution s;
int ans = s.fib(n); // 3
cout << ans << endl;
system("pause");
return 0;
}
复杂度分析:
- 时间复杂度:O(n) 需要计算每个元素的斐波那契数值
- 空间复杂度:O(n) 需要存储每个元素的斐波那契数值
注意事项:
- if (n <= 1) return n; 当n为0或1时,无法由递推公式推导得到,需要根据dp数组的含义直接返回结果,此处在实际编程过程中容易忽略。(所有动态规划题目都需要格外注意)
解法2:动态规划(优化版)
解题思路:利用"状态压缩"进行优化 → 由于当前数值仅依赖于前面两个数值,因此只需要维护两个数值 (后面将讲解的很多动规的题目其实都是当前状态依赖前两个,或者前三个状态,都可以做空间上的优化)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int fib(int n)
{
if (n <= 1) return n;
vector<int> dp(2, 0); // 优化:只需要维护两个数值即可,不需要记录整个序列
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};
int main()
{
int n = 4;
Solution s;
int ans = s.fib(n); // 3
cout << ans << endl;
system("pause");
return 0;
}
复杂度分析:
- 时间复杂度:O(n) 需要计算每个元素的斐波那契数值
- 空间复杂度:O(1) 无需存储每个元素的斐波那契数值(只需要维护两个数值即可,不需要记录整个序列)
2. 爬楼梯(方案个数)(斐波那契数列扩展)(LeetCode70)
题目描述:https://leetcode.cn/problems/climbing-stairs/description/
解法1:动态规划(基础版)
解题思路:动态规划五部曲
爬到第1层楼梯:有1种方法
爬到第2层楼梯:有2种方法 1+1(每次爬一个台阶)、2(一次爬两个台阶)
爬到第3层楼梯:有3种方法
1 +2(先爬一个台阶、再爬两个台阶) 由第1层楼梯过来
1+1 +1(每次爬一个台阶) 由第2层楼梯过来
2 +1(先爬两个台阶、再爬一个台阶) 由第2层楼梯过来
可见,到第三层楼梯的状态 可以由 第二层楼梯 和 第一层楼梯状态 推导出来
- Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]:爬到第i层楼梯的方法个数有dp[i]种
- Step2:确定递推公式 - 从dp[i]的定义可以看出,dp[i]可以有两个方向推出来 - dp[i-1]:上到第i-1层楼梯,有dp[i-1]种方法,再一步 跳一个台阶 即可到达第i层楼梯- dp[i-2]:上到第i-2层楼梯,有dp[i-2]种方法,再一步 跳两个台阶 即可到达第i层楼梯- dp[i] = dp[i-1] + dp[i-2]
- Step3:初始化dp数组 - 由递推公式可知,需要初始化前两个元素 - dp[1] = 1- dp[2] = 2- 注意:此处并不初始化dp[0],因为没有实际意义- 很多题解强行将dp[0]初始化为1,基本都是直接奔着答案去解释的(因为在递推的过程中i从2开始遍历本题就能过)
- Step4:确定遍历顺序 - 由递推公式可知,需要从前向后遍历
- Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int climbStairs(int n)
{
if (n <= 2) return n;
vector<int> dp(n+1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) // 注意:此处i是从3开始遍历
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
int main()
{
Solution s;
int ans = s.climbStairs(3);
cout << ans << endl;
system("pause");
return 0;
}
复杂度分析:
- 时间复杂度:O(n) 需要计算到达每层楼梯的方法个数
- 空间复杂度:O(n) 需要存储到达每层楼梯的方法个数
解法2:动态规划(优化版)
解题思路:利用"状态压缩"进行优化 → 由于当前数值仅依赖于前面两个数值,因此只需要维护两个数值 (动态规划的常见优化思路)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int climbStairs(int n)
{
if (n <= 2) return n;
vector<int> dp(3);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) // 注意:此处i是从3开始遍历
{
int sum = dp[1] + dp[2];
dp[1] = dp[2];
dp[2] = sum;
}
return dp[2];
}
};
int main()
{
Solution s;
int ans = s.climbStairs(3);
cout << ans << endl;
system("pause");
return 0;
}
复杂度分析:
- 时间复杂度:O(n) 需要计算到达每层楼梯的方法个数
- 空间复杂度:O(1) 无需存储每个元素的斐波那契数值(只需要维护两个数值即可,不需要记录整个序列)
3. 爬楼梯(最小花费)(LeetCode746)
题目描述:https://leetcode.cn/problems/min-cost-climbing-stairs/
解法1:动态规划(基础版)
解题思路:动态规划五部曲
- Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]:到达第i台阶所花费的最少体力为dp[i]
- Step2:确定递推公式 - 由于每次只能向上爬一个或者两个台阶,因此到达第i台阶有两个途径 - 从第i-1台阶跳1步:需要花费 dp[i-1]+cost[i-1]- 从第i-2台阶跳2步:需要花费 dp[i-2]+cost[i-2]- dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
- Step3:初始化dp数组 - 题目描述:可以选择从下标为0或下标为1的台阶开始爬楼梯- 到达第0个台阶是不花费体力,但从第0个台阶往上跳的话,需要花费cost[0]- 到达第1个台阶是不花费体力,但从第1个台阶往上跳的话,需要花费cost[1]- dp[0] = 0- dp[1] = 0
- Step4:确定遍历顺序 - 由递推公式可知,需要从前向后遍历
- Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int minCostClimbingStairs(vector<int>& cost)
{
vector<int> dp(cost.size()+1);
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= cost.size(); i++)
{
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()];
}
};
int main()
{
vector<int> cost{ 10,15,20 }; // 15
//vector<int> cost{ 1,100,1,1,1,100,1,1,100,1 }; // 6
Solution s;
int ans = s.minCostClimbingStairs(cost);
cout << ans << endl;
}
复杂度分析:
- 时间复杂度:O(n) 需要计算到达每层楼梯的最小体力
- 空间复杂度:O(n) 需要存储到达每层楼梯的最小体力
解法2:动态规划(优化版)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int minCostClimbingStairs(vector<int>& cost)
{
vector<int> dp(2);
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= cost.size(); i++)
{
int dpi = min(dp[0] + cost[i-2], dp[1] + cost[i-1]);
dp[0] = dp[1];
dp[1] = dpi;
}
return dp[1];
}
};
int main()
{
vector<int> cost{ 10,15,20 }; // 15
//vector<int> cost{ 1,100,1,1,1,100,1,1,100,1 }; // 6
Solution s;
int ans = s.minCostClimbingStairs(cost);
cout << ans << endl;
}
复杂度分析:
- 时间复杂度:O(n) 需要计算到达每层楼梯的最小体力
- 空间复杂度:O(1)
4. 不同路径(无障碍)(LeetCode62)
题目描述:https://leetcode.cn/problems/unique-paths/description/
解法1:动态规划(基础版)
解题思路:动态规划五部曲
- Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i][j]:从(0,0)出发到达(i,j)的不同路径有dp[i][j]条
- Step2:确定递推公式 - 机器人每次只能向下或者向右移动一步,因此到达(i,j)有两个途径 - 从(i-1,j)向下移动:dp[i-1][j] 从(0,0)出发,到(i-1,j)的不同路径个数- 从(i,j-1)向右移动:dp[i][j-1] 从(0,0)出发,到(i,j-1)的不同路径个数- dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- Step3:初始化dp数组 - 从(0,0)出发,到达第一行的任意位置,只有1种路径 → dp[0][j] = 1- 从(0,0)出发,到达第一列的任意位置,只有1种路径 → dp[i][0] = 1- 注意:只能向下或向右移动
- Step4:确定遍历顺序 - 由递推公式可知,需要从前向后、从上向下遍历
- Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int uniquePaths(int m, int n)
{
// 示例:m=3 n=7
// 1 1 1 1 1 1 1
// 1 2 3 4 5 6 7
// 1 3 6 10 15 21 28
// Step3:初始化dp数组
vector<vector<int>> dp(m, vector<int>(n, 0)); // 二维数组的初始化(重要)
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
// Step4:确定遍历顺序
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
// Step2:确定递推公式
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
int main()
{
Solution s;
int ans = s.uniquePaths(3, 7); // 28
cout << ans << endl;
system("pause");
return 0;
}
复杂度分析:
- 时间复杂度:O(m×n) 需要计算到达每一个位置的不同路径个数,两层for循环(第一层for循环遍历m-1行,第二层for循环遍历n-1列)
- 空间复杂度:O(m×n) 需要存储到达每一个位置的不同路径个数
解法2:动态规划(优化版)
解题思路:使用一维数组(可以理解为滚动数组)进行空间优化 → 不利于理解,但可以优化空间
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int uniquePaths(int m, int n)
{
// 示例:m=3 n=7
// 初始化一维数组 1 1 1 1 1 1 1
// i=1 1 2 3 4 5 6 7
// i=2 1 3 6 10 15 21 28
// Step3:初始化dp数组
vector<int> dp(n, 1);
// Step4:确定遍历顺序(只能先遍历行,后遍历列)
for (int i = 1; i < m; i++) // 遍历行时,只能从上向下遍历
{
for (int j = 1; j < n; j++) // 遍历列时,只能从前向后遍历
// for (int j = n-1; j > 0; j--) // 错误
{
// Step2:确定递推公式
// dp[j-1]:在计算dp[j]时,dp[j-1]已经计算完毕,因此dp[j-1]为第i行("新值") → 从(i,j-1)出发,向右移动
// dp[j](公式右侧):dp[j]还没有计算,因此dp[j]为第i-1行("旧值") → 从(i-1,j)出发,向下移动
dp[j] = dp[j - 1] + dp[j];
}
}
return dp[n - 1];
}
};
int main()
{
Solution s;
int ans = s.uniquePaths(3, 7); // 28
cout << ans << endl;
system("pause");
return 0;
}
复杂度分析:
- 时间复杂度:O(m×n) 需要计算到达每一个位置的不同路径个数
- 空间复杂度:O(n) 每一阶段仅存储一行中所有位置的信息(先计算完一行,再计算下一行)
5. 不同路径(有障碍)(LeetCode63)
题目描述:https://leetcode.cn/problems/unique-paths-ii/description/
解法1:动态规划(基础版)
解题思路:本题与不同路径(无障碍)的区别
- 区别1:dp数组的初始化- 不同路径1:直接将第一行和第一列初始化为1- 不同路径2:若某个位置存在障碍物,则该位置及其之后的所有位置均不可达
- 区别2:递推公式- 不同路径1:所有位置都可以计算递推公式- 不同路径2:若某个位置存在障碍物,则该位置的不同路径个数为0,无需计算递推公式,而是直接使用默认值(遇到障碍dp[i][j]保持0)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
int m = obstacleGrid.size(); // 网格的行数
int n = obstacleGrid[0].size(); // 网格的列数
// 若起点或终点存在障碍物,则表明终点不可达,直接返回路径个数0
if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
// Step3:初始化dp数组
// 若第一行存在障碍物,则该障碍物及其之后的所有位置均不可达;若第一行不存在障碍物,则所有位置均初始化为1
// 若第一列存在障碍物,则该障碍物及其之后的所有位置均不可达;若第一列不存在障碍物,则所有位置均初始化为1
// 注意代码里for循环的终止条件,一旦遇到obstacleGrid[i][0] == 1的情况,就停止dp[i][0]的赋值1的操作,dp[0][j]同理
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1; // 初始化第一列
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1; // 初始化第一行
// Step4:确定遍历顺序
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
// Step2:确定递推公式
// 当前位置不存在障碍物,执行if语句,计算达到该位置的不同路径个数
// 当前位置存在障碍物,不执行if语句,使用默认的初始化值0,表明该位置不可达 或 达到该位置的不同路径个数为0
if (obstacleGrid[i][j] == 0)
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
};
int main()
{
vector<vector<int>> obstacleGrid{ {0,0,0},{0,1,0},{0,0,0} }; // 2
//vector<vector<int>> obstacleGrid{ {0,1},{0,0} }; // 1
Solution s;
int ans = s.uniquePathsWithObstacles(obstacleGrid);
cout << ans << endl;
system("pause");
return 0;
}
复杂度分析:
- 时间复杂度:O(mxn)
- 空间复杂度:O(mxn)
注意事项:
- if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0; 若起点或终点存在障碍物,则表明终点不可达,直接返回路径个数0(易漏点)
解法2:动态规划(优化版)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
int m = obstacleGrid.size(); // 网格的行数
int n = obstacleGrid[0].size(); // 网格的列数
// 若起点或终点存在障碍物,则表明终点不可达,直接返回路径个数0
if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
// Step3:初始化dp数组
vector<int> dp(n, 0);
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[j] = 1;
// Step4:确定遍历顺序
for (int i = 1; i < m; i++)
{
for (int j = 0; j < n; j++)
{
// Step2:确定递推公式
// 对于第1列:若存在障碍物,则赋值为0;若不存在障碍物,保持不变
// 对于其余列:若存在障碍物,则赋值为0;若不存在障碍物,则利用递推公式推导
if (obstacleGrid[i][j] == 1) // 若存在障碍物(无论哪一列),则赋值为0
{
dp[j] = 0;
}
else if(j != 0) // 若不存在障碍物且非第1列,则利用递推公式
{
dp[j] = dp[j - 1] + dp[j];
}
// 注:以上代码不能修改如下
// if (obstacleGrid[i][j] == 1) dp[j] = 0; // 若存在障碍物,则赋值为0
// if (j != 0) dp[j] = dp[j - 1] + dp[j]; // 若不存在障碍物,则利用递推公式(第一列不存在障碍物,则延续上一行的结果,不需要任何操作)
}
}
return dp[n - 1];
}
};
int main()
{
vector<vector<int>> obstacleGrid{ {0,0,0},{0,1,0},{0,0,0} }; // 2
//vector<vector<int>> obstacleGrid{ {0,1},{0,0} }; // 1
Solution s;
int ans = s.uniquePathsWithObstacles(obstacleGrid);
cout << ans << endl;
system("pause");
return 0;
}
复杂度分析:
- 时间复杂度:O(mxn)
- 空间复杂度:O(n)
6. 整数拆分(LeetCode343)
待补充!!!
7. 不同的二叉搜索树(LeetCode96)
题目描述: https://leetcode.cn/problems/unique-binary-search-trees/description/
以"n=3"举例分析
- 当1为头结点时:右子树有两个节点,两个节点的布局 和 n=2时两棵树的布局 是一样的
- 当2为头结点时:左右子树都只有一个节点,一个节点的布局 和 n=1时只有一棵树的布局 是一样的
- 当3为头结点时:左子树有两个节点,两个节点的布局 和 n=2时两棵树的布局 是一样的 - dp[3]:元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量- 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量dp[2] * 左子树有0个元素的搜索树数量dp[0]- 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量dp[1] * 左子树有1个元素的搜索树数量dp[1]- 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量dp[0] * 左子树有2个元素的搜索树数量dp[2]- dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
解题思路:动态规划五部曲
- Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]:由i个节点组成的二叉搜索树的个数为dp[i]
- Step2:确定递推公式 - 假设头节点的数值为j(需要遍历头节点的所有可能)- dp[j-1]:由j-1个节点组成的二叉搜索树的个数(左子树的节点个数为j-1)- dp[i-j]:由i-j个节点组成的二叉搜索树的个数(右子树的节点个数为i-j)
- Step3:初始化dp数组 - dp[0] = 1- dp[1] = 1 - dp[2] = 2
- Step4:确定遍历顺序 - 从递推公式可以看出,i是由j-1和i-j推导而来,因此需要从前向后遍历- j从1遍历到i:j-1小于i;i-j小于i,因此i由小于i的项推导得到
- Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int numTrees(int n)
{
if (n == 1) return 1;
if (n == 2) return 2;
vector<int> dp(n + 1, 0);
dp[0] = 1; // 易错点:dp[0]不能为0,否则会导致左右子树的布局个数相乘为0
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) // 第一层for循环:遍历二叉搜索树中的节点个数
{
for (int j = 1; j <= i; j++) // 第二层for循环:遍历头节点的数值(状态)
{
dp[i] += (dp[j - 1] * dp[i - j]);
}
}
return dp[n];
}
};
int main()
{
//int n = 3; // 5
int n = 1; // 1
Solution s;
int ans = s.numTrees(n);
cout << ans << endl;
system("pause");
return 0;
}
注意事项:当结点个数为0时,是否需要初始化,应该初始化为什么?这是一个难点(易错点、易漏点)。
- dp[0] = 1; dp[0]不能为0,否则会导致左右子树的布局个数相乘为0
- 本题的解法不能进行状态压缩,因为每次计算dp[i]时,需要依赖前面的所有状态。
版权归原作者 华科大胡子 所有, 如有侵权,请联系我们删除。