目录
遞推公式不該是過於關注的點，它只是解題的一部分，別讓自己在解題時處於黑盒狀態
動態規劃每一個狀態一定是由上一個狀態推導出來，而貪心則是從局部選最優堆疊成全局最優
定義DP數組以及下標的含意
dp[i][j] i 代表甚麼意思，j代表甚麼意思
dp[i] i 代表甚麼意思，元素代表甚麼意思
遞推公式
根據遞推公式，確定DP數組如何初始化
確定遍歷順序
打印dp數組
看完之後才知道原來動態規劃是這樣處理的，在之前根本不知道這道題目跟動態規劃有關係，只在演算法課堂中有講解過，直到現在才比較清楚。
我自己用模擬的我發現跟509. 斐波那契数的規律很像，只是初始化由原本dp[0] = 0 改為1 就可以成功AC了，但如果要照著動規五部曲要細細地去分析這道題目，我還無法完全分析。
還是很瞎猜的作法，在這道題目我在初始化的時候把dp[0]的值設為1，但其實在題目的涵義上，dp[0]是沒有意義的，那我初始化應該是從1跟2去開始初始化而不是0，這樣也可以跟我一開始定義的數組下標去符合，整體解題思路才會比較連貫
看到的想法是比較大小去找比較小的數值去進行跌代，但是這個做法沒辦法找到最小的花費，直接看代碼隨想錄。
看完有點恍惚，原來這個跟前兩題其實差不多，只是思考的點要更細緻一點，我在看的過程中真的學習到很多，尤其是初始化的部分，原本我的想像是cost[0]跟cost[1]但是聽完之後才知道我誤解了，整體真的學習到了很多。
定義DP數組以及下標的含意
dp[i] 第i個斐波那契數的數值為dp[i]
遞推公式
F[i] = F[i - 1] + F[i - 2]
根據遞推公式，確定DP數組如何初始化
dp[0] = 0;
dp[1] = 1;
確定遍歷順序
從前向後遍歷
打印dp數組 (debug);
- class Solution {
- public:
- int fib(int n) {
- if(n <= 1) return n;
- vector<int> 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];
- }
- };
定義DP數組以及下標的含意
dp[i] 上去第i層樓梯的方法數為dp[i]
遞推公式
F[i] = F[i - 1] + F[i - 2]
根據遞推公式，確定DP數組如何初始化
dp[1] = 1;
dp[2] = 2;
確定遍歷順序
從前向後遍歷
打印dp數組 (debug);
- class Solution {
- public:
- int climbStairs(int n) {
- if(n <= 2) return n;
- vector<int> dp(n+1);
- dp[1] = 1;
- dp[2] = 2;
- for(int i = 3; i <= n; i++) {
- dp[i] = dp[i - 1] + dp[i - 2];
- }
- return dp[n];
- }
- };
定義DP數組以及下標的含意
dp[i] 代表的是到達下標i所需要的最小花費為dp[i];
遞推公式
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i -2] + cost[i - 2]);
dp[i - 1] + cost[i - 1]; dp[i - 1] 指的是前面跳得花費，cost[i - 1]則是當前的花費。
dp[i - 2] + cost[i - 2];
根據遞推公式，確定DP數組如何初始化
dp[0] = 0; 到達0的最小花費是0
dp[1] = 0; 到達1的最小花費是0
備註: 因為題目有說可以選擇0或1開始，並且是需要往上跳才需要對應的體力值消耗
確定遍歷順序
從前向後遍歷
打印dp數組 (debug);
- class Solution {
- public:
- int minCostClimbingStairs(vector<int>& cost) {
- vector<int> dp(cost.size() + 1);
- 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()];
- }
- };
今天學習上困難沒有那麼多，主要都是跟著學習，但覺得動態規劃是一個很好玩的主題，很期待後面的題目
今天大概學了1.5hr，整體理解上不難，但是有些誤區需要釐清，但相信隨著學習的深入，會越來越好的。
● 今日学习的文章链接和视频链接
理论基础
https://programmercarl.com/动态规划理论基础.html
视频：从此再也不怕动态规划了，动态规划解题方法论大曝光 ！| 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili
509. 斐波那契数
https://programmercarl.com/0509.斐波那契数.html
视频：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili
70. 爬楼梯
https://programmercarl.com/0070.爬楼梯.html
视频：带你学透动态规划-爬楼梯（对应力扣70.爬楼梯）| 动态规划经典入门题目_哔哩哔哩_bilibili
746. 使用最小花费爬楼梯
https://programmercarl.com/0746.使用最小花费爬楼梯.html
视频讲解：动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯_哔哩哔哩_bilibili