代码随想录算法训练营day32|动态规划part01
创始人
2024-11-04 21:08:55
0

动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。

第一题:509. Fibonacci Number

class Solution {     public int fib(int n) {         if (n < 2) return n;         int a = 0, b = 1, c = 0;         for (int i = 1; i < n; i++) {             c = a + b;             a = b;             b = c;         }         return c;     } } 
//非压缩状态的版本 class Solution {     public int fib(int n) {         if (n <= 1) return n;                      int[] dp = new int[n + 1];         dp[0] = 0;         dp[1] = 1;         for (int index = 2; index <= n; index++){             dp[index] = dp[index - 1] + dp[index - 2];         }         return dp[n];     } }

第二题:70. Climbing Stairs 

这题和第一题的斐波那契数是差不多的。

// 常规方式 public int climbStairs(int n) {     int[] dp = new int[n + 1];     dp[0] = 1;     dp[1] = 1;     for (int i = 2; i <= n; i++) {         dp[i] = dp[i - 1] + dp[i - 2];     }     return dp[n]; } 
// 用变量记录代替数组 class Solution {     public int climbStairs(int n) {         if(n <= 2) return n;         int a = 1, b = 2, sum = 0;          for(int i = 3; i <= n; i++){             sum = a + b;  // f(i - 1) + f(i - 2)             a = b;        // 记录f(i - 1),即下一轮的f(i - 2)             b = sum;      // 记录f(i),即下一轮的f(i - 1)         }         return b;     } }

第三题: 746. Min Cost Climbing Stairs 

// 方式一:第一步不支付费用 class Solution {     public int minCostClimbingStairs(int[] cost) {         int len = cost.length;         int[] dp = new int[len + 1];          // 从下标为 0 或下标为 1 的台阶开始,因此支付费用为0         dp[0] = 0;         dp[1] = 0;          // 计算到达每一层台阶的最小费用         for (int i = 2; i <= len; i++) {             dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);         }          return dp[len];     } } 
// 方式二:第一步支付费用 class Solution {     public int minCostClimbingStairs(int[] cost) {         int[] dp = new int[cost.length];         dp[0] = cost[0];         dp[1] = cost[1];         for (int i = 2; i < cost.length; i++) {             dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];         }         //最后一步,如果是由倒数第二步爬,则最后一步的体力花费可以不用算         return Math.min(dp[cost.length - 1], dp[cost.length - 2]);     } } 
// 状态压缩,使用三个变量来代替数组 class Solution {     public int minCostClimbingStairs(int[] cost) {         // 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。         int beforeTwoCost = 0, beforeOneCost = 0, currentCost = 0;         // 前两个台阶不需要费用就能上到,因此从下标2开始;因为最后一个台阶需要跨越,所以需要遍历到cost.length         for (int i = 2; i <= cost.length; i ++) {             // 此处遍历的是cost[i - 1],不会越界             currentCost = Math.min(beforeOneCost + cost[i - 1], beforeTwoCost + cost[i - 2]);             beforeTwoCost = beforeOneCost;             beforeOneCost = currentCost;         }         return currentCost;     } }

 

相关内容

热门资讯

推荐一款!牛牛房卡哪里有卖的海... 推荐一款!牛牛房卡哪里有卖的海航大厅/微信链接房间卡怎么购买海航大厅是一款非常受欢迎的游戏,咨询房/...
ia实测“在哪里买炸金花房卡哪... 随意玩是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:86909166许多玩家在游戏中会购买房卡来享...
我来教你/牛牛房卡代理新超圣/... 微信游戏中心:新超圣房卡在哪里买打开微信,添加客服微信【88355042】,进入游戏中心或相关小程序...
秒懂教程!拼三张房卡如何购买,... 拼三张是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:66336574许多玩家在游戏中会购买房卡来享...
IA解析/金花房卡代理零售天启... 天启联盟是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:【3329006910】或QQ:332900...
一分钟了解“微信群链接牛牛买房... 牛牛是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:44346008许多玩家在游戏中会购买房卡来享受...
正规平台有哪些,牛牛房卡制作链... 今 日消息,乐酷大厅房卡添加微信33549083 苹果今日发布了 iOS 16.1 正式版更新,简单...
秒懂教程!拼三张房卡如何购买,... 拼三张是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:56001354许多玩家在游戏中会购买房卡来享...
ia实测“如何在微信上购买金花... 金花是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:86909166许多玩家在游戏中会购买房卡来享受...
正规平台有哪些,金花房间怎么创... 流樱大厅/新道游是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:【3329006910】或QQ:33...
秒懂教程!微信炸金花房卡哪里有... 炸金花是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:71319951许多玩家在游戏中会购买房卡来享...
我来教你/牛牛房卡怎么获得乐酷... 您好!微信乐酷大厅大厅链接获取房卡可以通过以下几种方式购买: 1.微信渠道:(乐酷大厅)大厅介绍:...
一分钟了解“买房卡的金花房代理... 海贝之城是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:160470940许多玩家在游戏中会购买房卡...
我来教你/牛牛房卡官网玫瑰大厅... 我来教你/牛牛房卡官网玫瑰大厅/房卡链接怎么获取玫瑰大厅是一款非常受欢迎的游戏,咨询房/卡添加微信:...
科技实测!金花房卡批发价荣耀乐... 微信游戏中心:荣耀乐娱房卡在哪里买打开微信,添加客服微信【88355042】,进入游戏中心或相关小程...
一分钟推荐“创建金花房间链接教... 神皇大厅是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:160470940许多玩家在游戏中会购买房卡...
头条推荐!如何购买金花房卡皇豪... 皇豪互娱是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:【3329006910】或QQ:332900...
秒懂教程!拼三张房卡链接在哪弄... 拼三张是一款非常受欢迎的棋牌游戏,咨询房/卡添加微信:56001354许多玩家在游戏中会购买房卡来享...
重大通报,牛牛房卡哪里有卖的新... 今 日消息,新道游/皇豪互娱房卡添加微信33549083 苹果今日发布了 iOS 16.1 正式版更...
正版授权!牛牛房卡出售江山大厅... 江山大厅房卡更多详情添加微:33549083、 2、在商城页面中选择房卡选项。 3、根...