武侯区建设局网站,禹城网站制作,小程序wordpress视频,模板王ppt输入#xff1a;一个数组cost#xff0c;cost[i]表示越过第i个台阶的代价#xff08;可能是热量#xff0c;也可能是过路费#xff09; 输出#xff1a;走过这n个台阶#xff0c;需要的最小代价 规则#xff1a;一旦你为第i个台阶付出代价cost[i]#xff0c;那么你可以…输入一个数组costcost[i]表示越过第i个台阶的代价可能是热量也可能是过路费 输出走过这n个台阶需要的最小代价 规则一旦你为第i个台阶付出代价cost[i]那么你可以到达第i1个台阶也可以到达第i2个台阶。你可以从第0个或者第1个台阶开始走。 分析没什么好说的一步步走没走一步付出代价private void walk(int step,int currentcost) 表达站在第i个台阶付出了多少代价。 你可以试着把cache去掉当然是超时。加cache是因为如果你曾经花费代价10站在了第5个台阶那下次遇到需要花费代价15站在了第5个台阶就没必要进行走下去。因为代价肯定高嘛。
class Solution {private int mincost Integer.MAX_VALUE;private int[] cost;private int[] cache;private int n;public int minCostClimbingStairs(int[] cost) {this.cost cost;this.n cost.length;this.cache new int[n];walk(0,0);walk(1,0);return mincost;}private void walk(int step,int currentcost){if(stepn){mincost Math.min(mincost,currentcost);return;}if(cache[step]0 || currentcostcache[step]){cache[step] currentcost;walk(step1,currentcostcost[step]);walk(step2,currentcostcost[step]);}}
}动态规划分析初步分析得到能站点第i个台阶的代价应该是与第i-1和第i-2台阶有关。 之前很多从回溯法到动态规划都会发现dp[i]和回调函数的含义会有点变化。这次不会发生变化直接拿过来。
dp[i]表示能够到达第i个台阶需要的最小代价
dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]])
最后返回dp[n]public int minCostClimbingStairs(int[] cost) {int n cost.length;int[] dp new int[n1];dp[0] 0;dp[1] 0;for(int i2;in;i){dp[i] Math.min(dp[i-2]cost[i-2],dp[i-1]cost[i-1]);}return dp[n];}
