2024-11-30
1.2k 字
4 分钟
LeetCode-爬楼梯
题目
假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定n是一个正整数
示例1
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例2
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
《代码随想录》算法公开课
力扣题目链接
思路
首先，我们举几个栗子：
爬到第一层阶梯只有 一种方法
爬到第二层阶梯有两种方法
爬到第三层阶梯可以由第一层阶梯跨两步，或者由第二层阶梯跨一步
爬到第四层
2024-11-30
1k 字
4 分钟
动态规划入门
动态规划简介
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划五步曲
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
注：一些情况是递推公式决定了dp数组要如何初始化！
动态规划应该如何debug
当我们去学动态规划的题很容易出现看完题解，自己上手写代码一直通过不了，首先我们要明白，写动态规划，代码出问题很正常！
de
2024-11-29
1k 字
4 分钟
一维与二维前缀和与差分
什么是前缀和？
一维数组前缀和
例如数组nums = [1,2,3,4,5]
则其前缀和数组为qian = [1,3,6,10,15]，即qian数组的i索引位置处的值为nums数组索引0-i值的和
则有如下关系：nums[i] = qian[i] - qian[i-1]
注：使用该方法有一最大优势便是可以以(O1)的时间复杂度得到某块区间的总和，是典型的牺牲空间换取时间
二维数组前缀和
二维数组的应用和计算
二维数组前缀和是一种在二维矩阵上进行快速区域求和的技术，它是一维前缀和概念的扩展。在二维数组中，前缀和可以帮助我们快速计算任意子矩阵的元素和，这在处理图像处理或者某些区域查询
