松原市住房和城乡建设厅网站,现在做一个网站系统多少钱,有什么平台可以免费发布推广信息,wordpress tag 数据库动态规划算法6
LeetCode 279 完全平方数 2023.12.11
题目链接代码随想录讲解[链接]
int numSquares(int n) {//1确定dp数组#xff0c;其下标表示j的完全平方数的最少数量//3初始化#xff0c;将dp[0]初始化为0#xff0c;用于计算#xff0c;其他值设为INT_MAX用于递推…动态规划算法6
LeetCode 279 完全平方数 2023.12.11
题目链接代码随想录讲解[链接]
int numSquares(int n) {//1确定dp数组其下标表示j的完全平方数的最少数量//3初始化将dp[0]初始化为0用于计算其他值设为INT_MAX用于递推公式求最小vectorint dp(n1,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, vectorstring wordDict) {//用于搜索函数搜索某一子串string类型没有find()函数与循环体中注释语句配合使用//unordered_setstring wordSet(wordDict.begin(), wordDict.end());//1确定dp数组及下标含义dp[i]表示(0,i)子字符串能否被拼接出//3初始化dp[0]不能为false否则后续都为false其他值默认falsevectorbool 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
题目链接代码随想录讲解[链接]
#includebits/stdc.h
using namespace std;int main()
{//背包容量矿石种类int bagSize, sortSize;cin bagSize sortSize;//每种矿石的重量、价值、及数量vectorint weight(sortSize, 0);vectorint price(sortSize, 0);vectorint 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初始化所有背包在没放物品时默认价值为0vectorint dp(bagSize1, 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;
}
