首页 > 编程语言 >代码随想录算法训练营 | 动态规划 part01

代码随想录算法训练营 | 动态规划 part01

时间:2024-08-15 17:54:46浏览次数:18  
标签:return part01 训练营 随想录 爬楼梯 int cost 台阶 dp

509. 斐波那契数

509. 斐波那契数
状态转移方程:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

递归,太多重复计算

class Solution {
public:
    int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
};

动态规划
dp table ; dp[i] 表示数字i的Fibonacci数

class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;
        vector<int> dp(n + 1);
        // base case
        dp[0] = 0; 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 fib(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1;
        // 状态转移
        for (int i = 2; i <= n; i++) {
            int c = b + a;
            a = b;
            b = c;
        }
        return b;
    }
};

70. 爬楼梯

70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
dp[i] 表示爬到第i阶台阶的方法数;

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) {
            return n;
        }
        vector<int>dp(n + 1);
        // base case
        dp[1] = 1;
        dp[2] = 2;
        // 状态转移
        // n阶楼梯爬到楼顶方法:
        // 1. 爬 n-1 阶 + 1 阶
        // 2. 爬 n-2 阶 + 2 阶
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

同样只与前两个状态有关;也可以用滚动数组

746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

dp[i] 表示爬到第i阶台阶的最小花费;
爬到第i阶台阶:
可以由第i - 1阶向上爬一个台阶,并支付从楼梯第i - 1个台阶向上爬需要支付的费用cost[i - 1]
也可以由第i - 2阶向上爬两个台阶,并支付从楼梯第i - 2个台阶向上爬需要支付的费用cost[i - 2]

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1); // 爬到第 i 个台阶的最小总花费
        dp[0] = 0; dp[1] = 0; // 可以作为起点,无花费
        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()]; // 楼顶
    }
};

标签:return,part01,训练营,随想录,爬楼梯,int,cost,台阶,dp
From: https://blog.csdn.net/Fern_v/article/details/141145771

相关文章

  • 代码随想录算法训练营第一天 | 704. 二分查找,27. 移除元素
     704.二分查找题目链接:https://leetcode.cn/problems/binary-search/1,左闭右闭publicintsearch(int[]nums,inttarget){intlow=0;inthigh=nums.length-1;while(low<=high){intmid=(high+low)/2;if(num......
  • 代码随想录算法训练营第43天:动态规划part10:子序列问题
    300.最长递增子序列力扣题目链接(opensnewwindow)给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例1:输入:nums=[10,9,2......
  • 代码随想录day30 || 452 引爆气球,435 无重叠区间,763 划分字母区间
    452射爆气球funcfindMinArrowShots(points[][]int)int{ //思路,尝试按照startasc,endasc排序一下,取交集射爆 iflen(points)==1{ return1 } sort.Slice(points,func(i,jint)bool{ ifpoints[i][0]==points[j][0]{ returnpoints[i][1]<points......
  • 代码随想录Day15
    110.平衡二叉树(优先掌握递归)给定一个二叉树,判断它是否是平衡二叉树平衡二叉树是指该树所有节点的左右子树的深度相差不超过1。示例1:输入:root=[3,9,20,null,null,15,7]输出:true示例2:输入:root=[1,2,2,3,3,null,null,4,4]输出:false示例3:输入:root=[]输出:t......
  • 2024牛客暑期多校训练营9 C Change Matrix
    题目大意维护一个\(n\)阶矩阵\(A\),其中最开始\(A_{i,j}=\gcd(i,j)\),共有\(q\)次操作,每次操作将矩阵某一行或某一列同乘一个数\(y\),求每一次操作后矩阵的所有元素之和。对\(10^9+7\)取模。\(n,q\leq10^5\),且保证数据随机生成。思路根据欧拉函数的性质,有\[\sum_{c|i......
  • 【代码随想录】一、数组:3.双指针 - 977.有序数组的平方
    本文为977.有序数组的平方的解法,部分图文参考自代码随想录977.有序数组的平方。1.题目1:977.有序数组的平方1.1.解法1:直接排序classSolution{public:vector<int>sortedSquares(vector<int>&nums){for(inti=0;i<nums.size();i++){n......
  • 【代码随想录】一、数组:2.移除元素
    部分图文参考于:代码随想录-移除元素和力扣官方解法。1.题目1★:27.移除元素1.1.解法1:暴力解法考验对数组底层实现的理解:数组的元素是不能删的,只能覆盖。通过两层for循环来求解,外层for循环遍历数组元素,内层for循环将目标值进行覆盖。classSolution{public:intremove......
  • 【代码随想录】一、数组:1.二分查找
    部分图文参考于:代码随想录-二分查找,本文仅作为个人学习使用,如有侵权,请联系删除。1.概念二分查找也称折半查找(BinarySearch),是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知,运用二分搜索的前提是数组必须是有序的,这里需要注意的是,我们的输入不一定是数组,也......
  • 【代码随想录】一、数组:理论基础
    原文链接:代码随想录-数组理论基础,本文仅作为个人学习使用,如有侵权,请联系删除。数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力。数组是存放在连续内存空间上的相同类型数据的集合。数组可以方便的通过下标索引的方式获取到下......
  • 代码随想录训练营day20|235. 二叉搜索树的最近公共祖先,701.二叉搜索树中的插入操作,450
    二叉搜索树的最近公共祖先题目根据二叉搜索树的特性,它的公共祖先肯定是值夹在p和q之间的(满足此条件的第一个点)TreeNode*getroot(TreeNode*root,TreeNode*p,TreeNode*q){ if(rooot==NULL)returnNULL; if(root->val<p->val&&root->val<q->val){ returngetroot(r......