文章目錄
- 😉毛遂自薦
- ?題目
- 🤣題外話
- 😉正經點，解題思路
- 🌈代碼實作
- 💖最后
Code皮皮蝦 一個沙雕而又有趣的憨憨少年，和大多數小伙伴們一樣喜歡聽歌、游戲，當然除此之外還有寫作的興趣，emm…，日子還很長，讓我們一起加油努力叭🌈
👉話不多說，直達底部有粉絲專享福利！！！
😉毛遂自薦
毛遂自薦一下，給大家推薦一下自己的專欄😁，歡迎小伙伴們收藏關注😊
大廠面試題專欄
Java專欄
爬蟲專欄
力扣刷題專欄
更多專欄盡在主頁，點我😁！！！
?題目
673. 最長遞增子序列的個數
🤣題外話
本題是求最長遞增子序列的個數，而不是最長遞增子序列的長度，不會有小伙伴上來就給我擺出下面這個代碼的叭！不會吧不會吧(￣▽￣)
別問我是怎么知道的（手動滑稽）
300.最長子序列
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
for(int i = 0;i < nums.length;i++) {
dp[i] = 1;
}
int res = 1;
for(int i = 1;i < nums.length;i++) {
for(int j = 0;j < i;j++) {
if(nums[j] < nums[i]) {
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
res = Math.max(res,dp[i]);
}
return res;
}
}
😉正經點，解題思路
本題要的是，最長遞增子序列的個數，那么我們得知道最長是多少，才能再去求最長得序列個數是多少！
利用動態規劃，設定int[] dp = new int[nums.length];陣列記錄長度，設定int[] counts = new int[nums.length];記錄個數
那么狀態如何轉移呢?
如果有熟悉 300.最長子序列的小伙伴可能知道，我也不廢話
因為要遞增，所以?
當j < i && nums[j] < nums[i]的時候，就需要去判斷當前 dp[j] + 1 > dp[i]，
如果為true，說明：dp[j]是不能接在dp[i]前面，遞增序列有更大的長度，那么需要更新長度，既然有更大的長度，那么 counts[i] = counts[j]，因為count[i]所以記錄的個數已經無效了
但如果dp[j] + 1 == dp[i]，說明dp[j]是可以接在dp[i]前面的，所以要 counts[i] += counts[j];
🌈代碼實作
class Solution {
public int findNumberOfLIS(int[] nums) {
int len = nums.length;
if (len <= 1) return len;
int[] dp = new int[len];
int[] counts = new int[len];
//至少長度為1
Arrays.fill(counts, 1);
int maxLen = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
counts[i] = counts[j];
}else if (dp[j] + 1 == dp[i]) {
counts[i] += counts[j];
}
}
}
maxLen = Math.max(maxLen,dp[i]);
}
//通過比較maxLen，來進行個數的增加
int res = 0;
for (int i = 0; i < len; ++i) {
if (dp[i] == maxLen) {
res += counts[i];
}
}
return res;
}
}
💖最后
我是 Code皮皮蝦，一個熱愛分享知識的 皮皮蝦愛好者，未來的日子里會不斷更新出對大家有益的博文，期待大家的關注！！！
創作不易，如果這篇博文對各位有幫助，希望各位小伙伴可以一鍵三連哦！，感謝支持，我們下次再見~~~
公眾號干貨內容輸出，囊括Java、Python爬蟲、力扣題解、大廠面試題 四大系列，更有長時間總結的干貨資源分享，后臺回復：面試資料即可領取
最后，祝各位步步高升🚀🚀🚀
粉絲福利👇🏻👇🏻👇🏻
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/302498.html
標籤：java
下一篇：Java階段二：陣列和方法