directory
0.0.0-20240920062246-d0657495930a
Repository: https://github.com/yigmmk/leetcode.git
Documentation: pkg.go.dev
# Packages
* @lc app=leetcode.cn id=1137 lang=golang
*
* [1137] 第 N 个泰波那契数
*
* https://leetcode.cn/problems/n-th-tribonacci-number/description/
*
* algorithms
* Easy (60.94%)
* Likes: 291
* Dislikes: 0
* Total Accepted: 181.2K
* Total Submissions: 297.4K
* Testcase Example: '4'
*
* 泰波那契序列 Tn 定义如下：
*
* T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
*
* 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
*
*
*
* 示例 1：
*
* 输入：n = 4
* 输出：4
* 解释：
* T_3 = 0 + 1 + 1 = 2
* T_4 = 1 + 1 + 2 = 4
*
*
* 示例 2：
*
* 输入：n = 25
* 输出：1389537
*
*
*
*
* 提示：
*
*
* 0 <= n <= 37
* 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
*
*
*/.
* @lc app=leetcode.cn id=1139 lang=golang
*
* [1139] 最大的以 1 为边界的正方形
*
* https://leetcode.cn/problems/largest-1-bordered-square/description/
*
* algorithms
* Medium (49.51%)
* Likes: 130
* Dislikes: 0
* Total Accepted: 15.7K
* Total Submissions: 30.3K
* Testcase Example: '[[1,1,1],[1,0,1],[1,1,1]]'
*
* 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回
* 0。
*
*
*
* 示例 1：
*
* 输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
* 输出：9
*
*
* 示例 2：
*
* 输入：grid = [[1,1,0,0]]
* 输出：1
*
*
*
*
* 提示：
*
*
* 1 <= grid.length <= 100
* 1 <= grid[0].length <= 100
* grid[i][j] 为 0 或 1
*
*
*/.
* @lc app=leetcode.cn id=1140 lang=golang
*
* [1140] 石子游戏 II
*
* https://leetcode.cn/problems/stone-game-ii/description/
*
* algorithms
* Medium (66.27%)
* Likes: 216
* Dislikes: 0
* Total Accepted: 16.8K
* Total Submissions: 24.2K
* Testcase Example: '[2,7,9,4,4]'
*
* 爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
*
* 爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。
*
* 在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
*
* 游戏一直持续到所有石子都被拿走。
*
* 假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。
*
*
*
* 示例 1：
*
*
* 输入：piles = [2,7,9,4,4]
* 输出：10
* 解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 =
* 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。
*
*
* 示例 2:
*
*
* 输入：piles = [1,2,3,4,5,100]
* 输出：104
*
*
*
*
* 提示：
*
*
* 1 <= piles.length <= 100
* 1 <= piles[i] <= 10^4
*
*
*/.
* @lc app=leetcode.cn id=1143 lang=golang
*
* [1143] 最长公共子序列
*
* https://leetcode.cn/problems/longest-common-subsequence/description/
*
* algorithms
* Medium (64.98%)
* Likes: 1486
* Dislikes: 0
* Total Accepted: 398.8K
* Total Submissions: 613.8K
* Testcase Example: '"abcde"\n"ace"'
*
* 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
*
* 一个字符串的 子序列
* 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
*
*
* 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
*
*
* 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
*
*
*
* 示例 1：
*
*
* 输入：text1 = "abcde", text2 = "ace"
* 输出：3
* 解释：最长公共子序列是 "ace" ，它的长度为 3 。
*
*
* 示例 2：
*
*
* 输入：text1 = "abc", text2 = "abc"
* 输出：3
* 解释：最长公共子序列是 "abc" ，它的长度为 3 。
*
*
* 示例 3：
*
*
* 输入：text1 = "abc", text2 = "def"
* 输出：0
* 解释：两个字符串没有公共子序列，返回 0 。
*
*
*
*
* 提示：
*
*
* 1
* text1 和 text2 仅由小写英文字符组成。
*
*
*/.
* @lc app=leetcode.cn id=121 lang=golang
*
* [121] 买卖股票的最佳时机
*
* https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
*
* algorithms
* Easy (57.71%)
* Likes: 3334
* Dislikes: 0
* Total Accepted: 1.3M
* Total Submissions: 2.2M
* Testcase Example: '[7,1,5,3,6,4]'
*
* 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
*
* 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
*
* 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
*
*
*
* 示例 1：
*
*
* 输入：[7,1,5,3,6,4]
* 输出：5
* 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
* 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
*
*
* 示例 2：
*
*
* 输入：prices = [7,6,4,3,1]
* 输出：0
* 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
*
*
*
*
* 提示：
*
*
* 1
* 0
*
*
*/.
* @lc app=leetcode.cn id=122 lang=golang
*
* [122] 买卖股票的最佳时机 II
*
* https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
*
* algorithms
* Medium (72.84%)
* Likes: 2383
* Dislikes: 0
* Total Accepted: 1M
* Total Submissions: 1.4M
* Testcase Example: '[7,1,5,3,6,4]'
*
* 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
*
* 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
*
* 返回 你能获得的 最大 利润 。
*
*
*
* 示例 1：
*
*
* 输入：prices = [7,1,5,3,6,4]
* 输出：7
* 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4
* 。
* 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
* 总利润为 4 + 3 = 7 。
*
* 示例 2：
*
*
* 输入：prices = [1,2,3,4,5]
* 输出：4
* 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4
* 。
* 总利润为 4 。
*
* 示例 3：
*
*
* 输入：prices = [7,6,4,3,1]
* 输出：0
* 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
*
*
*
* 提示：
*
*
* 1 <= prices.length <= 3 * 10^4
* 0 <= prices[i] <= 10^4
*
*
*/.
* @lc app=leetcode.cn id=1223 lang=golang
*
* [1223] 掷骰子模拟
*
* https://leetcode.cn/problems/dice-roll-simulation/description/
*
* algorithms
* Hard (49.80%)
* Likes: 138
* Dislikes: 0
* Total Accepted: 7.4K
* Total Submissions: 13K
* Testcase Example: '2\n[1,1,2,2,2,3]'
*
* 有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
*
* 不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。
*
* 现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。
*
* 假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。
*
*
*
* 示例 1：
*
* 输入：n = 2, rollMax = [1,1,2,2,2,3]
* 输出：34
* 解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2
* 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。
*
*
* 示例 2：
*
* 输入：n = 2, rollMax = [1,1,1,1,1,1]
* 输出：30
*
*
* 示例 3：
*
* 输入：n = 3, rollMax = [1,1,1,2,2,3]
* 输出：181
*
*
*
*
* 提示：
*
*
* 1 <= n <= 5000
* rollMax.length == 6
* 1 <= rollMax[i] <= 15
*
*
*/.
* @lc app=leetcode.cn id=123 lang=golang
*
* [123] 买卖股票的最佳时机 III
*
* https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
*
* algorithms
* Hard (60.03%)
* Likes: 1651
* Dislikes: 0
* Total Accepted: 307.5K
* Total Submissions: 511.9K
* Testcase Example: '[3,3,5,0,0,3,1,4]'
*
* 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
*
* 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
*
* 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
*
*
*
* 示例 1:
*
*
* 输入：prices = [3,3,5,0,0,3,1,4]
* 输出：6
* 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
* 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
*
* 示例 2：
*
*
* 输入：prices = [1,2,3,4,5]
* 输出：4
* 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4
* 。
* 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
* 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
*
*
* 示例 3：
*
*
* 输入：prices = [7,6,4,3,1]
* 输出：0
* 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
*
* 示例 4：
*
*
* 输入：prices = [1]
* 输出：0
*
*
*
*
* 提示：
*
*
* 1
* 0
*
*
*/.
No description provided by the author
* @lc app=leetcode.cn id=1334 lang=golang
*
* [1334] 阈值距离内邻居最少的城市
*
* https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/description/
*
* algorithms
* Medium (60.96%)
* Likes: 182
* Dislikes: 0
* Total Accepted: 28.5K
* Total Submissions: 46.5K
* Testcase Example: '4\n[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]\n4'
*
* 有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表
* fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
*
* 返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。
*
* 注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
*
*
*
* 示例 1：
*
*
*
*
* 输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
* 输出：3
* 解释：城市分布图如上。
* 每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
* 城市 0 -> [城市 1, 城市 2]
* 城市 1 -> [城市 0, 城市 2, 城市 3]
* 城市 2 -> [城市 0, 城市 1, 城市 3]
* 城市 3 -> [城市 1, 城市 2]
* 城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。
*
*
* 示例 2：
*
*
*
*
* 输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]],
* distanceThreshold = 2
* 输出：0
* 解释：城市分布图如上。
* 每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
* 城市 0 -> [城市 1]
* 城市 1 -> [城市 0, 城市 4]
* 城市 2 -> [城市 3, 城市 4]
* 城市 3 -> [城市 2, 城市 4]
* 城市 4 -> [城市 1, 城市 2, 城市 3]
* 城市 0 在阈值距离 2 以内只有 1 个邻居城市。
*
*
*
*
* 提示：
*
*
* 2
* 1
* edges[i].length == 3
* 0 i < toi < n
* 1 i, distanceThreshold
* 所有 (fromi, toi) 都是不同的。
*
*
*/.
* @lc app=leetcode.cn id=1477 lang=golang
*
* [1477] 找两个和为目标值且不重叠的子数组
*
* https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/description/
*
* algorithms
* Medium (30.78%)
* Likes: 124
* Dislikes: 0
* Total Accepted: 8.3K
* Total Submissions: 26.8K
* Testcase Example: '[3,2,2,4,3]\n3'
*
* 给你一个整数数组 arr 和一个整数值 target 。
*
* 请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。
*
* 请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。
*
*
*
* 示例 1：
*
* 输入：arr = [3,2,2,4,3], target = 3
* 输出：2
* 解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。
*
*
* 示例 2：
*
* 输入：arr = [7,3,4,7], target = 7
* 输出：2
* 解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2
* 是最小值。
*
*
* 示例 3：
*
* 输入：arr = [4,3,2,6,2,3,4], target = 6
* 输出：-1
* 解释：我们只有一个和为 6 的子数组。
*
*
* 示例 4：
*
* 输入：arr = [5,5,4,4,5], target = 3
* 输出：-1
* 解释：我们无法找到和为 3 的子数组。
*
*
* 示例 5：
*
* 输入：arr = [3,1,1,1,5,1,2,1], target = 3
* 输出：3
* 解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。
*
*
*
*
* 提示：
*
*
* 1 <= arr.length <= 10^5
* 1 <= arr[i] <= 1000
* 1 <= target <= 10^8
*
*
*/.
No description provided by the author
No description provided by the author
No description provided by the author
* @lc app=leetcode.cn id=464 lang=golang
*
* [464] 我能赢吗
*
* https://leetcode.cn/problems/can-i-win/description/
*
* algorithms
* Medium (40.80%)
* Likes: 537
* Dislikes: 0
* Total Accepted: 40.5K
* Total Submissions: 99.2K
* Testcase Example: '10\n11'
*
* 在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100
* 的玩家，即为胜者。
*
* 如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
*
* 例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
*
* 给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回
* true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。
*
*
*
* 示例 1：
*
*
* 输入：maxChoosableInteger = 10, desiredTotal = 11
* 输出：false
* 解释：
* 无论第一个玩家选择哪个整数，他都会失败。
* 第一个玩家可以选择从 1 到 10 的整数。
* 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
* 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
No description provided by the author
* @lc app=leetcode.cn id=62 lang=golang
*
* [62] 不同路径
*
* https://leetcode.cn/problems/unique-paths/description/
*
* algorithms
* Medium (67.91%)
* Likes: 1957
* Dislikes: 0
* Total Accepted: 710.1K
* Total Submissions: 1M
* Testcase Example: '3\n7'
*
* 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
*
* 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
*
* 问总共有多少条不同的路径？
*
*
*
* 示例 1：
*
*
* 输入：m = 3, n = 7
* 输出：28
*
* 示例 2：
*
*
* 输入：m = 3, n = 2
* 输出：3
* 解释：
* 从左上角开始，总共有 3 条路径可以到达右下角。
* 1.
* @lc app=leetcode.cn id=64 lang=golang
*
* [64] 最小路径和
*
* https://leetcode.cn/problems/minimum-path-sum/description/
*
* algorithms
* Medium (69.85%)
* Likes: 1619
* Dislikes: 0
* Total Accepted: 545.9K
* Total Submissions: 781.2K
* Testcase Example: '[[1,3,1],[1,5,1],[4,2,1]]'
*
* 给定一个包含非负整数的 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
*
*
*
*
* 提示：
*
*
* m == grid.length
* n == grid[i].length
* 1 <= m, n <= 200
* 0 <= grid[i][j] <= 200
*
*
*/.
* @lc app=leetcode.cn id=70 lang=golang
*
* [70] 爬楼梯
*
* https://leetcode.cn/problems/climbing-stairs/description/
*
* algorithms
* Easy (54.05%)
* Likes: 2845
* Dislikes: 0
* Total Accepted: 1.1M
* Total Submissions: 2M
* Testcase Example: '2'
*
* 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
*
* 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
*
*
*
* 示例 1：
*
*
* 输入：n = 2
* 输出：2
* 解释：有两种方法可以爬到楼顶。
* 1.
* @lc app=leetcode.cn id=714 lang=golang
*
* [714] 买卖股票的最佳时机含手续费
*
* https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
*
* algorithms
* Medium (76.14%)
* Likes: 1028
* Dislikes: 0
* Total Accepted: 255K
* Total Submissions: 334.9K
* Testcase Example: '[1,3,2,8,4,9]\n2'
*
* 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
*
* 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
*
* 返回获得利润的最大值。
*
* 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
*
*
*
* 示例 1：
*
*
* 输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
* 输出：8
* 解释：能够达到的最大利润:
* 在此处买入 prices[0] = 1
* 在此处卖出 prices[3] = 8
* 在此处买入 prices[4] = 4
* 在此处卖出 prices[5] = 9
* 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
*
* 示例 2：
*
*
* 输入：prices = [1,3,7,5,10,3], fee = 3
* 输出：6
*
*
*
*
* 提示：
*
*
* 1 <= prices.length <= 5 * 10^4
* 1 <= prices[i] < 5 * 10^4
* 0 <= fee < 5 * 10^4
*
*
*/.
* @lc app=leetcode.cn id=72 lang=golang
*
* [72] 编辑距离
*
* https://leetcode.cn/problems/edit-distance/description/
*
* algorithms
* Medium (62.80%)
* Likes: 3243
* Dislikes: 0
* Total Accepted: 426K
* Total Submissions: 678.4K
* Testcase Example: '"horse"\n"ros"'
*
* 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
*
* 你可以对一个单词进行如下三种操作：
*
*
* 插入一个字符
* 删除一个字符
* 替换一个字符
*
*
*
*
* 示例 1：
*
*
* 输入：word1 = "horse", word2 = "ros"
* 输出：3
* 解释：
* horse -> rorse (将 'h' 替换为 'r')
* rorse -> rose (删除 'r')
* rose -> ros (删除 'e')
*
*
* 示例 2：
*
*
* 输入：word1 = "intention", word2 = "execution"
* 输出：5
* 解释：
* intention -> inention (删除 't')
* inention -> enention (将 'i' 替换为 'e')
* enention -> exention (将 'n' 替换为 'x')
* exention -> exection (将 'n' 替换为 'c')
* exection -> execution (插入 'u')
*
*
*
*
* 提示：
*
*
* 0 <= word1.length, word2.length <= 500
* word1 和 word2 由小写英文字母组成
*
*
*/.
* @lc app=leetcode.cn id=746 lang=golang
*
* [746] 使用最小花费爬楼梯
*
* https://leetcode.cn/problems/min-cost-climbing-stairs/description/
*
* algorithms
* Easy (65.92%)
* Likes: 1420
* Dislikes: 0
* Total Accepted: 384.5K
* Total Submissions: 583.3K
* Testcase Example: '[10,15,20]'
*
* 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
*
* 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
*
* 请你计算并返回达到楼梯顶部的最低花费。
*
*
*
* 示例 1：
*
*
* 输入：cost = [10,15,20]
* 输出：15
* 解释：你将从下标为 1 的台阶开始。
* - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
* 总花费为 15 。
*
*
* 示例 2：
*
*
* 输入：cost = [1,100,1,1,1,100,1,1,100,1]
* 输出：6
* 解释：你将从下标为 0 的台阶开始。
* - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
* - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
* - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
* - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
* - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
* - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
* 总花费为 6 。
*
*
*
*
* 提示：
*
*
* 2 <= cost.length <= 1000
* 0 <= cost[i] <= 999
*
*
*/.
* @lc app=leetcode.cn id=931 lang=golang
*
* [931] 下降路径最小和
*
* https://leetcode.cn/problems/minimum-falling-path-sum/description/
*
* algorithms
* Medium (67.54%)
* Likes: 327
* Dislikes: 0
* Total Accepted: 94.3K
* Total Submissions: 139.6K
* Testcase Example: '[[2,1,3],[6,5,4],[7,8,9]]'
*
* 给你一个 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：
*
*
*
*
* 输入：matrix = [[-19,57],[-40,-5]]
* 输出：-59
* 解释：如图所示，为和最小的下降路径
*
*
*
*
* 提示：
*
*
* n == matrix.length == matrix[i].length
* 1 <= n <= 100
* -100 <= matrix[i][j] <= 100
*
*
*/.