#### [120\. 三角形最小路径和](https://leetcode-cn.com/problems/triangle/)
使用 DFS（分治法）
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
超时
```
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
return helper(triangle, 0, 0);
}
int helper(vector<vector<int>>& triangle, int x, int y)
{
if (x == triangle.size() - 1)
return triangle[x][y];
int down = helper(triangle, x + 1, y);
int right = helper(triangle, x + 1, y + 1);
return min(down, right) + triangle[x][y];
}
};
```
记忆化搜索（本质：动态规划）
```
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int len = triangle.size();
vector<vector<int>> mem(len, vector<int>(len, -1));
return helper(triangle, mem, 0, 0);
}
int helper(vector<vector<int>>& triangle, vector<vector<int>>& mem, int x, int y)
{
if (x == triangle.size() - 1)
return triangle[x][y];
if (mem[x][y] != -1)
return mem[x][y];
int down = helper(triangle, mem, x + 1, y);
int right = helper(triangle, mem, x + 1, y + 1);
mem[x][y] = min(down, right) + triangle[x][y];
return mem[x][y];
}
};
```
动态规划就是把大问题变成小问题，并解决小问题重复计算的方法
动态规划和DFS的区别
* 二叉树子问题没有交集，所以大部分二叉树都是用递归或者分治法，即DFS，就可以解决
* 像triangle这种有重复走的情况，子问题有交集，所以可以用动态规划来解决
```
// 自下往上-二维
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int len = triangle.size();
if (len == 0)
return 0;
for (int i = len - 2; i >= 0; i--)
for (int j = 0; j < triangle[i].size(); j++)
{
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
}
return triangle[0][0];
}
};
```
#### [64\. 最小路径和](https://leetcode-cn.com/problems/minimum-path-sum/)
给定一个包含非负整数的*m* x *n* 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
超出时间限制
```
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
vector<int> result;
dfs(grid, 0, 0, 0, result);
sort(result.begin(), result.end());
return result[0];
}
void dfs(vector<vector<int>>& grid, int x, int y, int sum, vector<int>& result)
{
sum += grid[x][y];
int rowLen = grid.size();
int colLen = grid[0].size();
if (x == rowLen - 1 && y == colLen - 1)
{
result.push_back(sum);
return;
}
if (x == rowLen - 1)
dfs(grid, x, y + 1, sum, result);
else if (y == colLen - 1)
dfs(grid, x + 1, y, sum, result);
else
{
dfs(grid, x + 1, y, sum, result);
dfs(grid, x, y + 1, sum, result);
}
}
};
```
动态规划
```
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0) return 0;
int rowLen = grid.size();
int colLen = grid[0].size();
for (int i = rowLen - 2; i >= 0; i--)
{
grid[i][colLen - 1] += grid[i + 1][colLen - 1];
}
for (int i = colLen - 2; i >= 0; i--)
{
grid[rowLen - 1][i] += grid[rowLen - 1][i + 1];
}
for (int i = rowLen - 2; i >= 0; i--)
for (int j = colLen - 2; j >= 0; j--)
{
grid[i][j] += min(grid[i + 1][j], grid[i][j + 1]);
}
return grid[0][0];
}
};
```
#### [62\. 不同路径](https://leetcode-cn.com/problems/unique-paths/)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
超出时间限制
```
class Solution {
public:
int uniquePaths(int m, int n) {
int result = 0;
dfs(m, n, 1, 1, result);
return result;
}
void dfs(int m, int n, int x, int y, int& result)
{
if (x == m && y == n)
{
result++;
return;
}
if (x == m)
dfs(m, n, x, y + 1, result);
else if (y == n)
dfs(m, n, x + 1, y, result);
else
{
dfs(m, n, x, y + 1, result);
dfs(m, n, x + 1, y, result);
}
}
};
```
动态规划
```
class Solution {
public:
int uniquePaths(int m, int n) {
int result = 1;
vector<vector<int>> dp(m, vector<int>(n, 1));
for (int x = m - 2; x >= 0; x--)
for (int y = n - 2; y >= 0; y--)
dp[x][y] = dp[x][y + 1] + dp[x + 1][y];
return dp[0][0];
}
};
```
#### [63\. 不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
```
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.size() == 0)
return 0;
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<unsigned int>> dp(m, vector<unsigned int>(n, 0));
for (int x = m - 1; x >= 0; x--)
{
if (obstacleGrid[x][n - 1])
break;
dp[x][n - 1] = 1;
}
for (int y = n - 1; y >= 0; y--)
{
if (obstacleGrid[m - 1][y])
break;
dp[m - 1][y] = 1;
}
for (int x = m - 2; x >= 0; x--)
for (int y = n - 2; y >= 0; y--)
{
if (obstacleGrid[x][y])
dp[x][y] = 0;
else
dp[x][y] = dp[x][y + 1] + dp[x + 1][y];
}
return dp[0][0];
}
};
```
## 序列类型（40%）
#### [70\. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)
假设你正在爬楼梯。需要*n* 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：**给定*n*是一个正整数。
```
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
int g = 1;
int f = 2;
for (int i = 3; i <= n; i++)
{
f = f + g;
g = f - g;
}
return f;
}
};
```
#### [55\. 跳跃游戏](https://leetcode-cn.com/problems/jump-game/)
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
```
class Solution {
public:
bool canJump(vector<int>& nums) {
int most = 0;
for (int i = 0; i < nums.size(); i++)
{
if (i > most)
return false;
most = max(most, nums[i] + i);
}
return true;
}
};
```
#### [45\. 跳跃游戏 II](https://leetcode-cn.com/problems/jump-game-ii/)
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
```
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int result = 0;
int start = 0;
int end = 0;
while (end < n - 1)
{
int nextReach = end;
for (int i = start; i <= end; i++)
{
nextReach = max(nextReach, nums[i] + i);
}
start = end + 1;
end = nextReach;
result++;
}
return result;
}
};
```
#### [343\. 整数拆分](https://leetcode-cn.com/problems/integer-break/)
```cpp
// 记忆化搜索
class Solution {
private:
vector<int> mem;
int max3(int a, int b, int c) {
return max(a, max(b, c));
}
int breakInteger(int n) {
if (n == 1)
return 1;
if (mem[n] != -1)
return mem[n];
int res = -1;
for (int i = 1; i <= n - 1; ++i)
res = max3(res, i * (n - i), i * breakInteger(n-i));
mem[n] = res;
return res;
}
public:
int integerBreak(int n) {
assert(n >= 2);
mem = vector<int>(n+1, -1);
return breakInteger(n);
}
};
// 动态规划
class Solution {
private:
int max3(int a, int b, int c) {
return max(a, max(b, c));
}
public:
int integerBreak(int n) {
assert(n >= 2);
vector<int> mem(n+1, -1);
mem[0] = 1;
for (int i = 2; i <= n; ++i)
{
for (int j = 1; j <= i-1; ++j)
mem[i] = max3(mem[i], j * (i - j), j * mem[i-j]);
}
return mem[n];
}
};
```
- 空白目录
- 算法
- 排序
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 计数排序
- 桶排序
- 基数排序
- 希尔排序
- 堆排序
- 二分查找
- 最小堆
- 最小索引堆
- 平衡二叉树（AVL tree）
- bitmap位图
- 布隆过滤器
- hashmap
- topK
- 跳表
- LRU Cache
- kmp
- 最小堆和堆排序
- 最短路径
- C++
- 运行时类型判断RTTI
- C++反射
- 手动实现智能指针
- 序列化实现
- rpc实现
- std::forward
- 函数指针的妙用
- C/C++
- std::function
- 同步队列
- 线程池实现
- std::promise
- 深入理解虚函数
- extern "C" 关键字讲解
- 大端小端的区别
- 简历
- 简历1
- redis
- 数据结构和对象
- sds
- list
- zskiplist
- 腾讯云redis面试题总结
- redis集群部署
- LeetCode
- 目标
- go基础
- 算法快速入门
- 数据结构篇
- 二叉树
- 链表
- 栈和队列
- 二进制
- 基础算法篇
- 二分搜索
- 排序算法
- 动态规划
- 算法思维
- 递归思维
- 滑动窗口思想
- 二叉搜索树
- 回溯法
- 其他
- 剑指offer
- 笔记
- git代理加速
- Linux
- vim大法
- vscode远程不能跳转
- cmake
- 设计模式
- 单例模式
- 简单工厂模式
- 外观模式
- 适配器模式
- 工厂方法模式
- 抽象工厂模式
- 生成器模式
- 原型模式
- 中介者模式
- 观察者模式
- 访问者模式
- 命令模式
- 网络编程
- epoll reactor模式
- linux timerfd系列函数总结
- IO
- mapreduce
- 反射器
- leo通信库
- Mutex
- Condition
- thread
- raft
- 协程
- hook
- 定时器
- 别人的面试经验
- 面试题
- vector崩溃问题
- JAVA
- Linux java环境配置
- ucore
- lab1
- FreeNOS
- leveldb
- 刷题笔记
- 回文串
- 前缀树
- 字符串查找
- 查找两个字符串a,b中的最长公共子串
- 动态规划
- golang
- 顺序循环打印实现
- 数据结构
- rpc运用
- python
- 单例
- 深拷贝浅拷贝
- 链表
- python基础题
- mysql
- 事务
- Linux
- 共享内存
- 刷题记录
- 贪心算法
- 动态规划
- 面试
- 腾讯C++面试
- 微众面试JD
- 迅雷网络面试
- 学习网址
- rabbitMq