目錄

1.不同路徑

題解

2140. 解決智力問題

題解

2873. 有序三元組中的最大值?

題解

---

1.不同路徑

鏈接：62. 不同路徑

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。

問總共有多少條不同的路徑？

---

題解

這個機器人位于左上角位置，每次只能向右和向下移動

• 問從開始位置到終點一共有多少種不同的路徑。
• 我們下標從1開始計數，這樣就少了很多邊界情況。

接下來我們用記憶化搜索解決這個問題。

如果純記憶化搜索我們只要兩步就可以了。

• 第一步 先想出暴搜（遞歸）的代碼。
• 第二步 暴搜代碼改成記憶化搜索，但是前提是能否改！

1.暴搜（遞歸）

我們最后向求出的m,n位置有多少種不同的走法

• 那么就這樣搞dfs，dfs我給你兩個參數，dfs(i，j)
• 你直接給我返回1，1到達i，j有多少種走法。

具體dfs你內部怎么走我不關心，我相信你一定能夠完成任務。

• 接下來想想這個函數體 如何設計，我想從1，1到達這個三角的位置一共有多少種方式，其實只用關心兩個位置就可以。
• 因為想到達三角的位置，必須要從這兩個圓圈到達，要求只能向右走向下走。
• 如果此時我知道到達圓圈有多少種方式那在多走一步就走到三角了。
• 也就是說到達圓圈有多少種方式，到達這個三角也有多少種方式。

因此僅需要達到兩個圓圈有多少種方式加起來就是到達三角位置的方式 dfs(i-1，j) + dfs(i，j-1)。

遞歸出口 我們考慮某個位置的時候，我們僅會考慮它上面的位置以及左邊的位置。

• 有可能i=1的時候去考慮i-1不就越界了嗎
• i=0的時候不能從非法位置達到這里。
• 同理j=0也是一種非法情況，我們既要考慮上邊也要考慮左邊。因此

i == 0 || j == 0 return 0;

但還有一種隱藏遞歸出口

• 當i == 1 && j == 1的時候是位于起點的
• 上面和左邊都沒有所以需要特殊處理 i == 1 && j == 1 return 1

class Solution {
public:int uniquePaths(int m, int n) {//爆搜return dfs(m,n);}int dfs(int m,int n){//出口if(m==0 || n==0) return 0;if(m==1 && n==1) return 1;return dfs(m-1,n)+dfs(m,n-1);}
};

上面會超時，下面看看能否暴搜的代碼改成記憶化搜索。

在遞歸過程種發現大量重復的相同問題就可以用記憶化搜索。

記憶化搜索

我們發現在遞歸過程種發現大量重復的相同問題因此可以用記憶化搜索

搞一個備忘錄

• 遞歸之前，查找一下備忘錄
• 返回之前，把結果存在備忘錄中

搞一個備忘錄 上一道題是搞一個一維數組，但是這道題dfs函數里面是有兩個可變參數，i和j一直在變化。

• 里面的值是int，因此我可以搞一個int [m+1][n+1] 二維數組。
• 因為要訪問到m,n的位置。

進前 瞅瞅。return 前 存存

class Solution {
public:vector<vector<int>> memo;int uniquePaths(int m, int n) {//記憶化搜索memo.resize(m+1,vector<int>(n+1,0));return dfs(m,n);}int dfs(int m,int n){if(memo[m][n]) return memo[m][n];//出口if(m==0 || n==0) return 0;if(m==1 && n==1) return 1;memo[m][n]=dfs(m-1,n)+dfs(m,n-1);return dfs(m-1,n)+dfs(m,n-1);}
};

解下來把記憶化搜索改成動態規劃。

1. 多加一層的 初始化
2. 循環內 要注意起點的值 continue ，防止被修改

---

2140. 解決智力問題

鏈接：2140. 解決智力問題

給你一個下標從 0 開始的二維整數數組 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

這個數組表示一場考試里的一系列題目，你需要 按順序 （也就是從問題 0 開始依次解決），針對每個問題選擇 解決 或者 跳過 操作。解決問題 i 將讓你 獲得 pointsi 的分數，但是你將 無法 解決接下來的 brainpoweri 個問題（即只能跳過接下來的 brainpoweri 個問題）。如果你跳過問題 i ，你可以對下一個問題決定使用哪種操作。

• 比方說，給你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：

• • 如果問題 0 被解決了， 那么你可以獲得 3 分，但你不能解決問題 1 和 2 。
  • 如果你跳過問題 0 ，且解決問題 1 ，你將獲得 4 分但是不能解決問題 2 和 3 。

請你返回這場考試里你能獲得的 最高 分數。

---

題解

剛好今天的每日一題

• 暴力 選 or 不選 會超時

class Solution {
public:typedef long long ll;queue<vector<int>> q;ll ret;long long mostPoints(vector<vector<int>>& questions) {//dpdfs(questions,0,0);return ret;}void dfs(vector<vector<int>>& questions,int p,ll count){if(p>=questions.size()) //向下 再向上 //暴力 是會經歷兩次的{ret=max(ret,count);return;}
//選dfs(questions,p+questions[p][1]+1,count+questions[p][0]);
//不選dfs(questions,p+1,count); } 
};

采用 記憶化搜索，記錄 結果的記憶化遞歸，避免 重復進行

class Solution 
{int n = 0;unordered_map<int, long long> memo;
public:long long dfs(vector<vector<int>>& questions, int pos){if (pos >= n)return 0;if (memo.count(pos))return memo[pos];// 選 - 跳到 pos + brain + 1long long ret = questions[pos][0] + dfs(questions, pos + questions[pos][1] + 1);// 不選 - 跳到 pos + 1ret = max(ret, dfs(questions, pos + 1));memo[pos] = ret; //記錄 結果的記憶化遞歸return ret;}long long mostPoints(vector<vector<int>>& questions){n = questions.size();return dfs(questions, 0);}
};

采用動態規劃，優化

---

2873. 有序三元組中的最大值?

鏈接：2873. 有序三元組中的最大值 I

給你一個下標從 0 開始的整數數組 nums 。

請你從所有滿足 i < j < k 的下標三元組 (i, j, k) 中，找出并返回下標三元組的最大值。如果所有滿足條件的三元組的值都是負數，則返回 0 。

下標三元組 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

---

題解

暴力

class Solution {
public:typedef long long ll;long long maximumTripletValue(vector<int>& nums) {//暴力ll ret=0;int n=nums.size();for(int i=0;i<n-2;i++){for(int j=i+1;j<n-1;j++){for(int k=j+1;k<n;k++){ret = max(ret,(ll)(nums[i] - nums[j]) * nums[k]);//!!!強轉}}}return ret;}
};

注意 max 比較對 ll 的強轉~

解法二：

類比：11.盛水最多的容器

利用單調性來進行空間換時間

class Solution {
public:typedef long long ll;long long maximumTripletValue(vector<int>& nums) {//利用單調性int n=nums.size();if (n < 3) return 0;  // 🌟 新增邊界條件ll ret=0;vector<int> max_left(n,0);  //ivector<int> max_right(n,0);  //k//空間換時間for(int j=1;j<n;j++){max_left[j]=max(max_left[j-1],nums[j-1]);
//！！！！！存儲當前位置所對應的最大左右值}for(int j=n-2;j>=0;j--){max_right[j]=max(max_right[j+1],nums[j+1]);}for(int j=1;j<n-1;j++){ret=max(ret,(ll)(max_left[j]-nums[j])*max_right[j]);}return ret;}
};

//！！！！！存儲當前位置所對應的最大左右值