algorithm/Week_04/id_27/LeetCode_746_027.java at master · feixiangcode/algorithm · GitHub

History

56 lines (43 loc) · 1.7 KB

Raw

class Solution {

如果我们用一个数组dp[]来存放到达每一层所需要的花费值。

则则最终结果是求dp[cost.length]的值。

因为每次可以走1层或者2层，并且可以从0或者从1开始，所以可以得到dp[0]为0，dp[1]为0。

从2开始，dp[i]可以由通过dp[i-2]走2层或者通过dp[i-1]走一层到达，

而这i-2和i-1层所要花费的值分别为cost[i-2]和cost[i-1]，

所以，dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])。

该算法的空间复杂度为O(n)，时间复杂度为O(n)。

public int minCostClimbingStairs(int[] cost) {

int length = cost.length + 1;

int[] dp = new int[length];

dp[0] = 0;

dp[1] = 0;

for (int i = 2; i < length; i++) {

dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);

}

return dp[length - 1];

}

由于在i大于等于2的情况下，dp[i]只跟dp[i-1]和dp[i-2]接cost数组有关。

所以我们只需要用三个变量来存储结果即可，即dp0,dp1,dp2，这样的空间复杂度就变成了O(1)。

public int minCostClimbingStairs1(int[] cost) {

int length = cost.length + 1;

int dp0 = 0;

int dp1 = 0;

int dp2 = 0;

for (int i = 2; i < length; i++) {

dp2 = Math.min(dp0 + cost[i - 2] , dp1 + cost[i - 1]);

dp0 = dp1;

dp1 = dp2;

}

return dp2;

}

public static void main(String[] args) {

int[] cost = {10, 15, 20};

//System.out.println(new Solution().minCostClimbingStairs(cost));

int[] cost1 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};

System.out.println(new Solution().minCostClimbingStairs(cost1));

}

algorithm/Week_04/id_27/LeetCode_746_027.java at master · feixiangcode/algorithm · GitHub

Expand file tree

Breadcrumbs

LeetCode_746_027.java

Latest commit

History

Breadcrumbs

LeetCode_746_027.java

File metadata and controls