动态规划刷题练习

分手后的思念是犯贱 2023-10-03 17:42 33阅读 0赞

#### 动态规划刷题 ####

*  Day1
 *   *  1.斐波拉契数列
     *  2. 第 N 个泰波那契数
 *  Day2
 *   *  1.爬楼梯
     *  2.使用最小花费爬楼梯
 *  Day3
 *   *  1.打家劫舍
     *  2. 打家劫舍 II
     *  3.删除并获得点数

## Day1 ##

### 1.斐波拉契数列 ###

[斐波拉契数列题目][Link 1]  
[斐波拉契数列题解1][1]  
[斐波拉契数列题解2][2]  
滚动数组法

### 2. 第 N 个泰波那契数 ###

[第 N 个泰波那契数题目描述][N]  
[第 N 个泰波那契数题解][N 1]  
滚动数组法的实践

## Day2 ##

### 1.爬楼梯 ###

[爬楼梯题目][Link 2]  
[爬楼梯题解][Link 3]  
观察可发现其相当于斐波拉契数列，f(n)=f(n-1)+f(n-2),可用动态规划法或滚动数组法

### 2.使用最小花费爬楼梯 ###

[使用最小花费爬楼梯题目][Link 4]  
[使用最小花费爬楼梯题解][Link 5]  
找出状态转移方程:  
dp\[i\]=min(dp\[i-1\]+cost\[i-1\],dp\[i-2\]+cost\[i-2\])  
可用动态规划法递推或滚动数组法

## Day3 ##

### 1.打家劫舍 ###

[打家劫舍题目描述][Link 6]  
[打家劫舍题解][Link 7]  
需要隔一个取一个  
状态转移方程：dp\[i\]=max(dp\[i-2\]+nums\[i\],dp\[i-1\])

### 2. 打家劫舍 II ###

[打家劫舍 II题目描述][II]  
[打家劫舍 II题解][II 1]  
与“打家劫舍”区别在于为环状，所以第一个和最后一个不能同时偷，因此分为两种范围考虑：\[0,n-2\](选第一个不选最后一个）和\[1,n-1\](选最后一个，不选第一个）  
所以取两个范围进行动态规划后的较大值  
状态转移方程：dp\[i\]=max(dp\[i-2\]+nums\[i\],dp\[i-1\])

### 3.删除并获得点数 ###

[删除并获得点数题目描述][Link 8]  
[删除并获得点数题解][Link 9]  
本质上也是和打家劫舍类似，把i-1和i+1删除即为不能取相邻的数，而对于“x”可能不止一个，将每个“x”放入sum数组得到每个“x”相加后的和，对sum数组进行动态规划（滚动数组法），sum数组中取到的为所有“x”相加后的点数，从而得到能取得的最大点数。  
状态转移方程：dp\[i\]=max(dp\[i-2\]+nums\[i\],dp\[i-1\])  
**-----------------------------持续更新------------------------------------------------**

[Link 1]: https://leetcode-cn.com/problems/fibonacci-number/
[1]: https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/
[2]: https://leetcode-cn.com/problems/fibonacci-number/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-labuladong/
[N]: https://leetcode-cn.com/problems/n-th-tribonacci-number/
[N 1]: https://leetcode-cn.com/problems/n-th-tribonacci-number/solution/di-n-ge-tai-bo-na-qi-shu-by-leetcode-sol-kn16/
[Link 2]: https://leetcode-cn.com/problems/climbing-stairs/
[Link 3]: https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
[Link 4]: https://leetcode-cn.com/problems/min-cost-climbing-stairs/
[Link 5]: https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/shi-yong-zui-xiao-hua-fei-pa-lou-ti-by-l-ncf8/
[Link 6]: https://leetcode-cn.com/problems/house-robber/
[Link 7]: https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
[II]: https://leetcode-cn.com/problems/house-robber-ii/
[II 1]: https://leetcode-cn.com/problems/house-robber-ii/solution/da-jia-jie-she-ii-by-leetcode-solution-bwja/
[Link 8]: https://leetcode-cn.com/problems/delete-and-earn/
[Link 9]: https://leetcode-cn.com/problems/delete-and-earn/solution/shan-chu-bing-huo-de-dian-shu-by-leetcod-x1pu/