沧州网站建设代理价格,国内网站备案要多久,直通车关键词怎么选 选几个,WordPress网页描述标签目录
斐波那契类型
746.使用最小花费爬楼梯 矩阵
120. 三角形最小路径和 斐波那契类型
746.使用最小花费爬楼梯
给你一个整数数组 cost #xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用#xff0c;即可选择向上爬一个或者两个台阶。…目录
斐波那契类型
746.使用最小花费爬楼梯 矩阵
120. 三角形最小路径和 斐波那契类型
746.使用最小花费爬楼梯
给你一个整数数组 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 。思路 class Solution {public int minCostClimbingStairs(int[] cost) {int arr[] new int[cost.length];arr[0] cost[0];arr[1] cost[1];for(int i 2; i cost.length; i){arr[i] Math.min(arr[i-1],arr[i-2])cost[i];}return Math.min(arr[cost.length-2],arr[cost.length-1]);}
} 矩阵
120. 三角形最小路径和
给定一个三角形 triangle 找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 1 的两个结点。也就是说如果正位于当前行的下标 i 那么下一步可以移动到下一行的下标 i 或 i 1 。
自底向上 在执行最后一行之后dp[]的每个下标都有对应的值 以此类推 遍历结果之后dp[0]会存储每次相邻的数之间的最小值直接返回dp[0]即可 class Solution {public int minimumTotal(ListListInteger triangle) {int[] dp new int[triangle.size()1]; //triangle.size()表triangle的大小for(int row triangle.size() - 1; row 0 ; row--){for(int i 0; i row; i){dp[i] Math.min(dp[i],dp[i1])triangle.get(row).get(i); //triangle.get(row).get(i)获取当前行下标为i的元素}}return dp[0];}
}
