LeetCode_Java_动态规划系列（1）（题目+思路+代码）
目录
斐波那契类型
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(List<List<Integer>> 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[i+1])+triangle.get(row).get(i); //triangle.get(row).get(i)获取当前行下标为i的元素
}
}
return dp[0];
}
}原文地址：https://blog.csdn.net/weixin_53415203/article/details/136252069
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！