@[songyuxuan090318](/user/730157) 我认为递推就是dp的特殊情况
by arrowpoint @ 2024-04-26 21:22:57
@[arrowpoint](/user/741839) 请问能展开讲讲吗?
by songyuxuan090318 @ 2024-04-26 22:19:09
@[songyuxuan090318](/user/730157) 对于一个dp,如果存在一种对于所有可能状态的编号方式,使每种编号的状态可以且只可以由它状态编号-1的状态转移而来,那么这个dp就是递推
by arrowpoint @ 2024-04-26 22:29:52
# dp动态规划
通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
>简单来说,动态规划其实就是,给定一个问题,我们把它拆成一个个子问题,直到子问题可以直接解决。然后呢,把子问题答案保存起来,以减少重复计算。再根据子问题答案反推,得出原问题解的一种方法。
### 动态规划核心思想
- 动态规划最核心的思想,就在于拆分子问题,记住过往,减少重复计算。
---
# 递归
递归是一种解决问题的有效方法,在递归过程中,函数将自身作为子例程调用。
>简单说程序调用自身的编程技巧叫递归。递归的思想是把一个大型复杂问题层层转化为一个与原问题规模更小的问题,问题被拆解成子问题后,递归调用继续进行,直到子问题无需进一步递归就可以解决的地步为止
- 使用递归需要避免出现死循环,为了确保递归正确工作,递归程序应该包含2个属性:
1. 基本情况(bottom cases),基本情况用于保证程序调用及时返回,不在继续递归,保证了程序可终止。
2. 递推关系(recurrentce relation),可将所有其他情况拆分到基本案例。
by LiXinHaoJun @ 2024-04-26 22:32:20
@[songyuxuan090318](/user/730157) 更通俗地说:如果把所有状态看作点,把可能转移看作边,如果形成的图是一条链,那么就是递推
by arrowpoint @ 2024-04-26 22:32:33
@[LiXinHaoJun](/user/1003631) 你引用错了,他说的是递推
by arrowpoint @ 2024-04-26 22:33:08