動態規劃算法6

LeetCode 279 完全平方數 2023.12.11

• 題目鏈接
• 代碼隨想錄講解[鏈接]
  

int numSquares(int n) {//1確定dp數組，其下標表示j的完全平方數的最少數量//3初始化，將dp[0]初始化為0，用于計算，其他值設為INT_MAX用于遞推公式求最小vector<int> dp(n+1,INT_MAX);dp[0] = 0;//2確定遞推公式，背包j值的最小完全平方數數量=min(背包值j-i*i的最小完全平方數量+1, 之前遍歷的dp[j])//因為是求具體值，而非排列數或組合數，所以先遍歷背包或者物品均可for (int i = 1; i <= sqrt(n); i++){for(int j = i*i; j <= n; j++){//背包j值的最小完全平方數數量=min(背包值j-i*i的最小完全平方數量+1, 之前遍歷的dp[j])dp[j] = min(dp[j-i*i]+1, dp[j]);}}return dp[n];
}

---

LeetCode 139 單詞拆分 2023.12.11

• 題目鏈接
• 代碼隨想錄講解[鏈接]
  

bool wordBreak(string s, vector<string>& wordDict) {//用于搜索函數搜索某一子串，string類型沒有find()函數，與循環體中注釋語句配合使用//unordered_set<string> wordSet(wordDict.begin(), wordDict.end());//1確定dp數組及下標含義，dp[i]表示(0,i)子字符串能否被拼接出//3初始化，dp[0]不能為false，否則后續都為false；其他值默認falsevector<bool> dp(s.size()+1, false);dp[0] = true;string cur;//2確定遞推公式，4確定遍歷順序//dp[i]表示(0,i)子字符串能否被拼接出，當(j,i)子字符串在字典中且(0,j)子字符串能被拼接出時dp[i]為true//該題為完全背包問題，且具有排列順序，所以先遍歷背包后遍歷物品for (int i = 1; i <= s.size(); i++){for(int j = 0; j <= i; j++){//背包容量為i，判斷(j,i)與(0,j)是否可拼接cur = s.substr(j, i-j);//if(wordSet.find(cur) != wordSet.end() && dp[j] == true)if(find(wordDict.begin(), wordDict.end(), cur) != wordDict.end() && dp[j] == true)dp[i] = true;}}return dp[s.size()];
}

---

卡碼網 56 攜帶礦石資源(多重背包) 2023.12.11

• 題目鏈接
• 代碼隨想錄講解[鏈接]
  

#include<bits/stdc++.h>
using namespace std;int main()
{//背包容量，礦石種類int bagSize, sortSize;cin >> bagSize >>sortSize;//每種礦石的重量、價值、及數量vector<int> weight(sortSize, 0);vector<int> price(sortSize, 0);vector<int> num(sortSize, 0);for(int i = 0; i < sortSize; i++)cin >> weight[i];for(int i = 0; i < sortSize; i++)cin >> price[i]; for(int i = 0; i < sortSize; i++)cin >> num[i];//1確定dp數組及下標含義，這里表示容量為i的背包能裝礦石的最大價值//3初始化，所有背包在沒放物品時默認價值為0vector<int> dp(bagSize+1, 0);//2確定遞推公式，4確定遍歷順序//遞推公式中，k表示第i中物品的個數，容量為j的背包最大價值=//max(上次遍歷物品的j容量背包最大價值，j-k*weight[i]容量大小的背包的最大價值+k個i物品的價值)for(int i = 0; i < sortSize; i++){for(int j = bagSize; j >= weight[i]; j--){for(int k = 1; k <= num[i] && j >= k*weight[i]; k++){dp[j] = max(dp[j-k*weight[i]] + k*price[i], dp[j]);}}}cout << dp[bagSize] << endl;return 0;
}

---