LeetCode_Java_动态规划系列（1）（题目+思路+代码）

目录

斐波那契类型

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(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];}
}