动态规划dp_4

一.背包

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

二.题

1.

思路：dp五部曲，思路在注释

/*
dp[i]表示：到达第 i 个台阶有dp[i]种方法
状态转移方程：dp[i] = dp[i-1] + dp [i-2] + dp[i-3] +  .... + dp[i-m]; 
既有：dp[i] +=dp[i-j];
初始化：从1到m都初始化为1
遍历方向，从下往上遍历
*/#include <iostream>
#include <vector>using namespace std;int main(){int n,m;cin>>n>>m;vector<int>dp(n+1);for(int i = 1; i <= m; i++)dp[i] = 1;for(int i = 2; i <= n; i++){for(int j = 1;j <= m && j < i; j++){dp[i] += dp[i-j];}}cout<<dp[n];return 0;
}

 2.

思路：dp五部曲，思路在注释

/*
dp[i]：表示当钱为 i 时，最小的组成方式为dp[i]
状态转移方程：遍历钱有dp[i] = min(dp[i],dp[i-j]+1)
初始化：dp[0] = 1;
遍历顺序：先背包，后钱
*/class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int>dp(amount+1,INT_MAX);dp[0] = 0;for(int i = 1; i <= amount; i++){for(int j = coins.size()-1; j>=0; j--){int coin = coins[j];if(i>=coin&&dp[i-coin]!=INT_MAX)dp[i] = min(dp[i],dp[i-coin]+1);}}if(dp[amount]==INT_MAX)return -1;else return dp[amount];}
};

3. 

思路：五部曲，注释

/*
dp[i]:当数为 i 时，完全平方数之和最小数量为dp[i]
状态转移方程：dp[i] = min(dp[i],dp[i-j*j]+1)
初始化：dp[0] = 0;
遍历顺序：都行
*/class Solution {
public:int numSquares(int n) {vector<int>dp(n+1,INT_MAX);dp[0] = 0;for(int i = 1; i <= n;i++){for(int j = 1; j * j<= i; j++){dp[i] = min(dp[i],dp[i - j * j]+1);}}return dp[n];}
};

 4.这个题得收藏

 

思路： 

1. 确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

1. 确定递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

1. dp数组如何初始化

从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。

那么dp[0]有没有意义呢？

dp[0]表示如果字符串为空的话，说明出现在字典里。

但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

1. 确定遍历顺序

题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。

还要讨论两层for循环的前后顺序。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++) {   // 遍历背包for (int j = 0; j < i; j++) {       // 遍历物品string word = s.substr(j, i - j); //substr(起始位置，截取的个数)if (wordSet.find(word) != wordSet.end() && dp[j]) {dp[i] = true;}}}return dp[s.size()];}
};

5.多重背包

思路：01背包的变种题型，只需要多加一层for循坏来控制住次数即可

#include <iostream>
#include <vector>
using namespace std;int C,N;int main(){cin>>C>>N;vector<int>dp(C+1,0);// dp数组vector<int>weight(N+1);vector<int>value(N+1);vector<int>nums(N+1);for(int i = 1;i <= N;i++) cin>>weight[i];for(int i = 1;i <= N;i++) cin>>value[i];for(int i = 1;i <= N;i++) cin>>nums[i];for(int i = 0; i <= N; i++){  // 物品for(int j = C; j >= weight[i]; j--){  //背包for(int k = 1; k <= nums[i] && (j - k * weight[i])>=0; k++){dp[j] = max(dp[j],dp[j - k * weight[i]] + k * value[i]);}}}cout<<dp[C];return 0;
}

6.

思路：dp五部曲，思路在注释

/*
dp[i]:数组的含义为从 1 到 i 家 可偷取的最大金额为 dp[i]
状态转移方程：对于 i 号房子时 有 偷与不偷 俩个状态
偷 i 时 有 dp[i-2] + val[i]
不偷 i 时 有 dp[i-1]
既有 dp[i] = max(dp[i-1],dp[i-2]+val[i]);
初始化：对于 1 和 2房间来说，1是必偷的房间，而对于 2考虑max(val[1],val[2])
遍历顺序：从前往后
*/
class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];else if(nums.size()==2)return max(nums[0],nums[1]);vector<int>dp(nums.size());dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);for(int i = 2;i < nums.size(); i++){dp[i] = max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.size()-1];}
};

 7.

思路：dp五部曲，思路在注释

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 1) return nums[0]; if (nums.size() == 2) return max(nums[0], nums[1]); vector<int> dp1(nums.size());dp1[0] = nums[0];dp1[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size() - 1; i++) {dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);}vector<int> dp2(nums.size());dp2[0] = 0;dp2[1] = nums[1];for (int i = 2; i < nums.size(); i++) {dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);}return max(dp1[nums.size() - 2], dp2[nums.size() - 1]);}
};

 8.

思路：注释

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}// 长度为2的数组，0：不偷，1：偷vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);// 偷cur，那么就不能偷左右节点。int val1 = cur->val + left[0] + right[0];// 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};

9.

思路：贪心和动态规划

贪心

class Solution {
public:int maxProfit(vector<int>& prices) {int cost = INT_MAX, profit = 0;for (int price : prices) {cost = min(cost, price);profit = max(profit, price - cost);}return profit;}
};

 dp

/*
买入的价格是随着遍历更新最小值的
dp则是买入后更新的获利最大值dp[i] : 表示当第 i 天卖出的最大值
状态转移方程：dp[i] = max(dp[i-1],prices[i] - min_in)
初始化：dp[0] = 0;
遍历顺序：前到后*/class Solution {
public:int maxProfit(vector<int>& prices) {if (n == 0) return 0;int minprice = prices[0];vector<int> dp (prices.size(), 0);for (int i = 1; i < prices.size(); i++){minprice = min(minprice, prices[i]);dp[i] = max(dp[i - 1], prices[i] - minprice);}return dp[n - 1];}
};

10.

思路：五部曲，思路在注释

/*
dp含义
dp[i][0]: 表示为从第 1 天到 i 天持有股票时利润最大值为dp[i][0]
dp[i][1]: 表示为从第 1 天到 i 天不持有股票利润最大值为dp[i][1]
状态转移方程：
dp[i][0] = max(dp[i - 1][0],dp[i - 1][1] + prices[i]); // 手不持股票
dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] - prices[i]); // 手持股票
初始化：
dp[0][0] = 0
dp[0][1] = -prices[0];
遍历顺序：
关系由递推得到，所以从头到尾
*/
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>>dp(prices.size(),vector<int>(2));dp[0][0] = 0;dp[0][1] = -prices[0];for(int i = 1;i < prices.size(); i++){dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);}return dp[prices.size()-1][0];}
};

 11.算法竞赛进阶指南

思路:诶呦，我的妈呀 ，这是什么题？

找规律，先看小的n = 1，n = 2，n = 3的情况，然后调用递归函数

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
char mp[730][730];
void f(int n, int x, int y) {if (n == 1)mp[x][y] = 'X';else {int m = pow(3, n - 2);f(n - 1, x, y);f(n - 1, x + 2 * m, y);f(n - 1, x, y + 2 * m);f(n - 1, x + m, y + m);f(n - 1, x + 2 * m, y + 2 * m);}
}
int main() {int n;while (1) {cin >> n;if (n == -1) return 0;int c = pow(3, n - 1);memset(mp, ' ', sizeof(mp));f(n, 0, 0);for (int i = 0; i < c; i++) {for (int j = 0; j < c; j++) cout << mp[i][j];cout << endl;}cout << '-' << endl;}return 0;
}