題解 | #最小花費爬樓梯#
最小花費爬樓梯
http://fangfengwang8.cn/practice/9b969a3ec20149e3b870b256ad40844e
import java.util.Scanner; // 注意類名必須為 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = in.nextInt(); } // int process1 = process(arr, 0, 0); // int process2 = process(arr, 1, 0); // System.out.println(Math.min(process1, process2)); System.out.println(dp(arr)); } //嘗試方法,超時了 public static int process(int[] arr, int index, int free) { int len = arr.length - 1; if (index == len) { return free + arr[index];//通過最后一個臺階登頂 } if (index > len) { return free;//沒通過最后一個臺階登頂 } free += arr[index]; //走一步 int one = process(arr, index + 1, free); //走兩步 int tow = process(arr, index + 2, free); //取最小值 return Math.min(one, tow); } //動態(tài)規(guī)劃 public static int dp(int[] arr) { int len = arr.length; int[] dp = new int[len]; dp[len - 1] = arr[len - 1]; dp[len - 2] = arr[len - 2]; for (int i = dp.length - 3; i >= 0; i--) { dp[i] = arr[i] + Math.min(dp[i + 1], dp[i + 2]); } return Math.min(dp[0], dp[1]); } }