線性dp

LeetCode題單， 從記憶化搜索到遞推
Pre：
從最初狀態到最終狀態等價，那么從最終狀態開始和最初狀態開始結果一樣。
遞歸時不會產生其他負面結果，即無論何時進入遞歸，只要遞歸參數相同，結果就相同。
那么可采用數組記憶遞歸結果，若有重復進入遞歸狀態則直接返回結果。

Pipeline：

1. 確定dfs 代表的含義， 從最終狀態開始
2. 確定遞歸出口
3. 寫dfs 轉移表達式
4. 翻譯為遞推， 遞歸出口即為初始條件， dfs 轉移表達式 即為 狀態轉移方程

時間復雜度： 單個狀態 乘以 計算當前單個狀態所需要的時間

爬樓梯 https://leetcode.cn/problems/climbing-stairs/

使用最小花費爬樓梯 https://leetcode.cn/problems/min-cost-climbing-stairs/

class Solution {
public:// dfs(i) 第n個臺階所需要的最小花費// dfs(i) = min(dfs(i - 1) + nums[i - 1], dfs(i - 2) + nums[i - 2]);vector <int> f;int dfs(vector<int>& cost, int n){if(n <= 1) return 0;if(f[n] != -1) return f[n];return f[n] = min(dfs(cost, n - 1) + cost[n - 1], dfs(cost, n - 2) + cost[n - 2]);}int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();f.resize(n + 1, -1);return dfs(cost, cost.size());}
};

class Solution {
public:// dfs(i) 第n個臺階所需要的最小花費// dfs(i) = min(dfs(i - 1) + nums[i - 1], dfs(i - 2) + nums[i - 2]);vector <int> f;int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();f.resize(n + 1, 0);f[0] = 0, f[1] = 0;for(int i = 2;i <= n;i ++){f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);}return f[n];}
};

空間優化，當前狀態只和前一兩個狀態有關，優化到O(1)

class Solution {
public:// dfs(i) 第n個臺階所需要的最小花費// dfs(i) = min(dfs(i - 1) + nums[i - 1], dfs(i - 2) + nums[i - 2]);int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();int f0 = 0, f1 = 0, newF = 0;for(int i = 2;i <= n;i ++){newF = min(f1 + cost[i - 1], f0 + cost[i - 2]);f0 = f1;f1 = newF;}return f1;}
};

377. 組合總和 Ⅳ https://leetcode.cn/problems/combination-sum-iv/

class Solution {
public:vector <int> f;int dfs(int i, vector<int>& nums){if(i == 0) return 1;if(f[i] != -1) return f[i];int res = 0;for(auto x: nums){if(x <= i){res += dfs(i - x, nums);}}return f[i] = res;}int combinationSum4(vector<int>& nums, int target) {f.resize(1005, -1);return dfs(target, nums);}
};

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector <unsigned > f(target + 1);f[0] = 1;for(int i = 1;i <= target;i ++){for(auto x : nums) {if(i >= x){f[i] += f[i - x];}}}return f[target];}
};

2466. 統計構造好字符串的方案數 https://leetcode.cn/problems/count-ways-to-build-good-strings/

2467. 統計打字方案數 https://leetcode.cn/problems/count-number-of-texts/

2468. 刪除并獲得點數 https://leetcode.cn/problems/delete-and-earn/

2469. 打家劫舍 II https://leetcode.cn/problems/house-robber-ii/

LCR 166. 珠寶的最高價值 https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/

01背包和完全背包

多維dp