网络营销企业网站优化,拖拽式建站,百度推广网址是多少,设计公司名称大全与寓意前言#xff1a; 昨天的题做过之后#xff0c;今天的题基本上都很简单#xff0c;但是要注重一下细节。
第一题#xff1a; 简介#xff1a;
动态规划五部曲#xff1a;
1.确定dp数组的含义 dp[i]#xff1a;爬到有i个台阶的楼顶#xff0c;有dp[i]种方法
2.确定dp…前言 昨天的题做过之后今天的题基本上都很简单但是要注重一下细节。
第一题 简介
动态规划五部曲
1.确定dp数组的含义 dp[i]爬到有i个台阶的楼顶有dp[i]种方法
2.确定dp公式 i:可以看作本次的物品值 j:可以看作背包容量 dp[j] dp[j-i];
3.确定如何初始化dp数组 dp[0] 1;
4.确定如何遍历数组 先遍历背包再遍历物品因为我们先迈一步再迈两步 还是 先迈两步再迈一步 是有区别的 for(int j0;jn;j){for(int i1;im;i){if(j-i0)dp[j] dp[j-i];}}
5.打印数组看是否正确
代码实现
#include iostream
#include vector
using namespace std;int palou(int m,int n){vectorint dp(n1,0);dp[0] 1;for(int j0;jn;j){for(int i1;im;i){if(j-i0)dp[j] dp[j-i];}}return dp.back();
}int main(){int m,n;cinnm;coutpalou(m,n);return 0;
}
第二题 简介
我认为本题的重点在于如何初始化dp数组自己做时在那里吃了亏。
动规五部曲分析如下
确定dp数组以及下标的含义 dp[j]凑足总额为j所需钱币的最少个数为dp[j] 2.确定递推公式 递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]); 如果放入就加一个金币不放入就不加。 3.dp数组如何初始化 首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;然后考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。
代码如下
vectorint dp(amount 1, INT_MAX);
dp[0] 0;4.确定遍历顺序 本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列。如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。所以本题的两个for循环的关系是外层for循环遍历物品内层for遍历背包或者外层for遍历背包内层for循环遍历物品都是可以的 5.举例推导dp数组 dp[amount]为最终结果。
代码实现 //dp[j]表示组成j 所需最少硬币个数int coinChange(vectorint coins, int amount) {vectorint dp(amount1,INT_MAX);dp[0]0;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){if (dp[j - coins[i]] ! INT_MAX)dp[j] min(dp[j],dp[j-coins[i]]1); }}if(dp.back()INT_MAX)return -1;elsereturn dp.back();}
第三题 简介 本题和上一题十分相似只不过我们在遍历时要注意完全平方数就是物品可以无限件使用凑个正整数n就是背包问凑满这个背包最少有多少物品这样本题是不是就很清晰了。
代码实现
先遍历背包再遍历物品
int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { // 遍历背包for (int j 1; j * j i; j) { // 遍历物品dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];}
先遍历物品再遍历背包 int numSquares(int n) {if(n4)return n;vectorint dp(n1,INT_MAX);dp[0] 0;for(int i1;i*in;i){for(int ji*i;jn;j){dp[j] min(dp[j],dp[j-i*i]1);}}return dp.back();}
总结
今天使用感觉更加得心应手了还需努力
