最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界新动态：【算法训练营day38】动态规划理论基础 LeetCode509. 斐波那契数 LeetCode70. 爬楼梯 LeetCode746. 使用最小花费爬楼梯

来源：博客园


(资料图)

动态规划理论基础

动态规划的解题步骤。

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

LeetCode509. 斐波那契数

题目链接：509. 斐波那契数

独上高楼，望尽天涯路

刚接触动态规划，学习为主，直接看题解视频。

慕然回首，灯火阑珊处

简单的动态规划题目，dp[i]表示的是第i项斐波那契数的值，递推公式和dp数组如何初始化已经给出，遍历顺序从前向后。

class Solution {public:    int fib(int n) {        if (n < 2) return n;        vector dp(n + 1);        dp[0] = 0;        dp[1] = 1;        for (int i = 2; i <= n; i++) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[n];    }};

LeetCode70. 爬楼梯

题目链接：70. 爬楼梯

独上高楼，望尽天涯路

思路对了，慢慢找到感觉了。

慕然回首，灯火阑珊处

dp[i]表示的是上到爬到第i阶台阶的方法数，需要注意的是应该从dp[1]开始初始化，dp[0]本身没有实际意义。

class Solution {public:    int climbStairs(int n) {        if (n < 2) return 1;        vector dp(n + 1);        dp[1] = 1; // 不应该从dp[0]开始初始化，dp[0]本身没有实际意义。        dp[2] = 2;        for (int i = 3; i <= n; i++) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[n];    }};

LeetCode746. 使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯

独上高楼，望尽天涯路

有感觉了，dp[i]表示的是上到爬到第i阶台阶的最小花费。

class Solution {public:    int minCostClimbingStairs(vector& cost) {        vector dp(cost.size() + 1);        dp[0] = 0;        dp[1] = 0;        for (int i = 2; i < cost.size() + 1; i++) {            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);        }        return dp.back();    }};

慕然回首，灯火阑珊处

思路一样。

关键词： 灯火阑珊处 动态规划 望尽天涯路