永久免费建站空间,网站开发项目实训总结,优秀网站首页,在线短链接生成器70 爬楼梯 #xff08;进阶)
爬楼梯问题在我们刚开始学习动态规划的时候作为入门的问题。当时题目考虑的是1或2种走法。如果将能走的台阶设为M#xff0c;则能产生进阶的题目。通过求解完全背包问题得到。
题目如下#xff1a;
题目页面
如果最多能走m个台阶#xff0c…70 爬楼梯 进阶)
爬楼梯问题在我们刚开始学习动态规划的时候作为入门的问题。当时题目考虑的是1或2种走法。如果将能走的台阶设为M则能产生进阶的题目。通过求解完全背包问题得到。
题目如下
题目页面
如果最多能走m个台阶那么1,2,...,m种走法就是物品走到楼顶就是背包。因为先走5再走1和先走1再走5是不一样的因此这道题是排列问题所以背包容量要放在循环外面。
递归公式 dp[i] dp[i - j] 代码如下
#include iostream
#include vector
using namespace std;
int main() {int n, m;while (cin n m) {vectorint dp(n 1, 0);dp[0] 1;for (int i 1; i n; i) { // 遍历背包for (int j 1; j m; j) { // 遍历物品if (i - j 0) dp[i] dp[i - j];}}cout dp[n] endl;}
}
Leetcode: 322 零钱兑换
基本规律
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
基本思路
1、确定下标
dp[i]表示凑足总额为i所需钱币的最少个数为dp[j]
2、递推公式
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1所以dp[j] min(dp[j - coins[i]] 1, dp[j]);
3、初始化
考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。
这里涉及到一个代码的写法
vectorint dp(amount 1, INT_MAX);
dp[0] 0;
4、循环逻辑
因为本题寻找的是最小所以无关物品和背包的关系为了代码好写选择了外层for循环遍历物品内层for遍历背包。
时间复杂度: O(n * amount)
空间复杂度: O(amount)
代码如下
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, INT_MAX);dp[0] 0;for(int i 0; i coins.size(); i){for(int j coins[i]; j amount; j){if(dp[j - coins[i]] ! INT_MAX){dp[j] min(dp[j - coins[i]] 1, dp[j]);}}}if (dp[amount] INT_MAX) return -1;return dp[amount];}
};
Leetcode: 279 完全平方数
1、下标和含义
dp[j]和为j的完全平方数的最少数量为dp[j]
2、递推公式
和上题基本一样只不过物品变成了平方数。
3、遍历顺序
遍历背包和物品都可以。
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for(int j 0; j n; j){//遍历背包for(int i 1; i*i j; i){//遍历物品注意当小于背包容量的时候停止dp[j] min(dp[j - i*i] 1, dp[j]);}}return dp[n];}
};
代码随想录
