爬樓梯進(jìn)階版

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 一步一個(gè)臺(tái)階，兩個(gè)臺(tái)階，三個(gè)臺(tái)階，…，直到 m個(gè)臺(tái)階。問(wèn)有多少種不同的方法可以爬到樓頂呢？

1. dp數(shù)組以及下標(biāo)名義

dp[j]：爬到j(luò)層一共有多少種方法。

2. 遞歸公式

遞推公式：dp[j] += dp[j - i];

3. dp數(shù)組如何初始化

dp[0] = 1;

4. 遍歷順序:顛倒兩個(gè)for循環(huán)順序，先遍歷背包再遍歷物品

5. 代碼

class Solution {
public:
    int climbStairs(int n) {
        vector<int> 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];
            }
        }
        return dp[n];
    }
};

322. 零錢兌換:硬幣可以重復(fù)選取

1. dp數(shù)組以及下標(biāo)名義

dp[i]：目標(biāo)整數(shù)為i的背包所能湊的最少硬幣個(gè)數(shù)。

2. 遞歸公式

coin[0] = 1時(shí)，dp[1]=1.dp[2] = 2;…dp[11]=11;
coin[1] = 2時(shí)，dp[1]=1;dp[2]=1;dp[3]=2;dp[4]=2;dp[5]=3;dp[6]=3;dp[7]=4;dp[8]=4
coin[2] = 5時(shí)，dp[1]=1;dp[2]=1;dp[3]=2;dp[4]=2;dp[5]=1；dp[6] =2
dp[i] = min(dp[i], dp[i - coins[j]] + 1);

3. dp數(shù)組如何初始化

dp[0] = 0;目標(biāo)和為0 所以是0個(gè)硬幣

4. 遍歷順序：組合與排列都可以，因?yàn)椴挥绊懕绢}求解

5. 代碼

class Solution {
public://完全背包問(wèn)題
    int coinChange(vector<int>& coins, int amount) {
      vector<int>dp(amount + 1, INT_MAX); 
      dp[0] = 0;
        for(int j = 0; j < coins.size(); j++) {//遍歷物品
              for(int i = coins[j]; i <= amount; i++) {//遍歷背包
              if(dp[i - coins[j]] != INT_MAX) {// 如果dp[j - coins[i]]是初始值則跳過(guò)
                   dp[i] = min(dp[i], dp[i - coins[j]] + 1);
              }
          }
      }
      if(dp[amount] == INT_MAX) return -1;
      return dp[amount];
    }
};

和之前一樣的寫法，用 if(i - coins[j] >= 0) ，但是vector里面要用double,因?yàn)槌跏蓟癁檎偷淖畲笾盗?class Solution {
public://完全背包問(wèn)題
    int coinChange(vector<int>& coins, int amount) {
      vector<double>dp(amount + 1, INT_MAX); 
      dp[0] = 0;
        for(int j = 0; j < coins.size(); j++) {//遍歷物品
             cout<<"coin "<< j<<" :";
              for(int i = coins[j]; i <= amount ; i++) {//遍歷背包
              //if(dp[i - coins[j]] != INT_MAX) {// 如果dp[j - coins[i]]是初始值則跳過(guò)
                   if(i - coins[j] >= 0) {
                   dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                 //  cout<<i<<":"<<dp[i]<<" ";
              }
              //cout<<endl;
          }

      }
      if(dp[amount] == INT_MAX) return -1;
      return dp[amount];
    }
};

279. 完全平方數(shù)

1. dp數(shù)組以及下標(biāo)名義

dp[j]：目標(biāo)為j的完全平方數(shù)最少的數(shù)量。

2. 遞歸公式

1時(shí)，dp[1]=1.dp[2] = 2;…;
2時(shí)，dp[1]=1;dp[2]=2;dp[3]=3;dp[4]=1;dp[5]=2;dp[6]=3;dp[7]=4;dp[8]=2
3時(shí)，dp[1]=1;dp[2]=1;dp[3]=2;dp[4]=2;dp[5]=2;dp[6]=3;dp[7]=4;dp[8]=2；dp[9]=1;dp[10]=2
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
遞推公式：dp[j] = min(dp[j],dp[j - i *i] +1);

3. dp數(shù)組如何初始化

dp[0] = 0;文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-470316.html

4. 遍歷順序:組合與排列都可以，因?yàn)椴挥绊懕绢}求解

5. 代碼

class Solution {
public:
    int numSquares(int n) {
        vector<double>dp(n + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i <= sqrt(n); i++) {
            for(int j = i * i; j <= n; j++) {
                if(j - i * i >= 0)
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];

    }
};

到了這里，關(guān)于day 45:爬樓梯進(jìn)階版；322. 零錢兌換；279. 完全平方數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！