最小路径题库
三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例1:
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例2:
输入：triangle = [[-10]]
输出：-10
方案 动态规划
思路:
- 状态定义:
dp[i][j]表示从三角形顶部走到位置(i,j)的最小路径和 - 状态转移方程: 每一步只能移动到下一行相邻的节点上，因此要想走到位置
(i,j)，上一步就只能在位置(i-1,j-1)或者位置(i-1,j)。我们在这两个位置中选择一个路径和较小的来进行转移，则方程为:dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+c[i][j]。其中c[i][j]表示位置(i,j)对应的元素值。
- 当
j=0时,dp[i-1][j-1]没有意义，则方程为:dp[i][0]=dp[i-1][0]+c[i][0] - 当
j=i时，dp[i-1][j]没有意义，则方程为:dp[i][i]=dp[i-1][i-1]+c[i][i]
- 初始化状态: dp 元素初始为 0
- 问题答案:
dp[n-1][0]到dp[n-1][n-1]中的最小值，其中n是三角形的行数
:::details 优化空间前
function minimumTotal(triangle) {
const len=triangle.length;
const dp=new Array(len).fill(0).map(()=>new Array(len).fill(0));
dp[0][0]=triangle[0][0];
for(let i=1;i<len;i++){
dp[i][0]=dp[i-1][0]+triangle[i][0];
for(let j=1;j<i;j++){
dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
}
dp[i][i]=dp[i-1][i-1]+triangle[i][i];
}
let minTotal=dp[len-1][0];
for(let i=1;i<len;i++){
minTotal=Math.min(minTotal,dp[len-1][i]);
}
return minTotal;
};
:::
上述dp[i][j]只与dp[i-1][……]有关，而与dp[i-2][……]及之前的状态无关，因此我们不必存储这些无关的状态。然后我们从i到0递减地枚举j
:::details 优化空间后
function minimumTotal(triangle) {
const len=triangle.length;
const dp=new Array(len).fill(0);
dp[0]=triangle[0][0];
for(let i=1;i<len;i++){
dp[i]=dp[i-1]+triangle[i][i];
for(let j=i-1;j>0;j--){
dp[j]=Math.min(dp[j-1],dp[j])+triangle[i][j];
}
dp[0]+=triangle[i][0];
}
let minTotal=dp[0];
for(let i=1;i<len;i++){
minTotal=Math.min(minTotal,dp[i]);
}
return minTotal;
};
:::
性能分析:
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例1:
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例2:
输入：grid = [[1,2,3],[4,5,6]]
输出：12
方案 动态规划
思路:
- 状态定义:
dp[i][j]表示从左上角出发到(i,j)位置的最小路径和。 - 状态转移方程:
- dp[0][0]=grid[0][0]
- 当
i>0且j=0时，dp[i][0]=dp[i-1][0]+grid[i][0] - 当
i=0且j>0时，dp[0][j]=dp[0][j-1]+grid[0][j] - 当
i>0且j>0时，`dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
- 初始化状态:
- 问题答案:
dp[m-1][n-1]的值即为最小路径和
:::details 点击查看代码
function minPathSum(grid) {
const row=grid.length;
const col=grid[0].length;
if(!grid||row==0||col==0){
return 0;
}
let dp=new Array(row).fill(0).map(()=>new Array(col).fill(0));
dp[0][0]=grid[0][0];
for(let i=1;i<row;i++){
dp[i][0]=dp[i-1][0]+grid[i][0];
}
for(let i=1;i<col;i++){
dp[0][i]=dp[0][i-1]+grid[0][i];
}
for(let i=1;i<row;i++){
for(let j=1;j<col;j++){
dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[row-1][col-1];
};
:::
性能分析:
- 时间复杂度: O(mn)
- 空间复杂度: O(mn)
下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例1:
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：下面是两条和最小的下降路径，用加粗+斜体标注：
[[2,1,3], [[2,1,3],
[6,5,4], [6,5,4],
[7,8,9]] [7,8,9]]
示例2:
输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：下面是一条和最小的下降路径，用加粗+斜体标注：
[[-19,57],
[-40,-5]]
方案 动态规划
思路:
- 状态定义:
dp[i][j]表示从位置为(i,j)的元素开始的下降路径最小和 - 状态转移方程: 由题可知，位置
(i,j)可以下降到(i+1,j-1),(i+1,j)和(i+1,j+1)三个位置，则状态方程为:dp[i][j]=matrix[i][j]+min(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]) - 初始化状态:
- 问题答案:
dp[0][i]中的最小值
:::details 点击查看代码
function minFallingPathSum(matrix) {
const row=matrix.length;
const col=matrix[0].length;
for(let i=row-2;i>=0;i--){
for(let j=0;j<col;j++){
let best=matrix[i+1][j];
if(j>0){
best=Math.min(best,matrix[i+1][j-1])
}
if(j+1<row){
best=Math.min(best,matrix[i+1][j+1]);
}
matrix[i][j]+=best;
}
}
let minPathSum=Infinity;
for(let item of matrix[0]){
minPathSum=Math.min(minPathSum,item);
}
return minPathSum;
};
:::
性能分析:
- 时间复杂度：O(N^2)
- 空间复杂度: O(N^2)
形成字符串的最短路径
对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的子序列。
给定源字符串 source 和目标字符串 target，找出源字符串中能通过串联形成目标字符串的子序列的最小数量。如果无法通过串联源字符串中的子序列来构造目标字符串，则返回 -1。
示例1:
输入：source = "abc", target = "abcbc"
输出：2
解释：目标字符串 "abcbc" 可以由 "abc" 和 "bc" 形成，它们都是源字符串 "abc" 的子序列。
示例2:
输入：source = "abc", target = "acdbc"
输出：-1
解释：由于目标字符串中包含字符 "d"，所以无法由源字符串的子序列构建目标字符串。
示例3:
输入：source = "xyz", target = "xzyxz"
输出：3
解释：目标字符串可以按如下方式构建： "xz" + "y" + "xz"。
方案 贪心
function shortestWay(source, target) {
let result=0;
let tar=0;
let prev=tar;
while(tar<target.length){
prev=tar;
for(let i=0;i<source.length;i++){
if(source[i]==target[tar]){
tar++;
}
}
if(prev==tar){
return -1;
}
result++;
}
return result;
};