[Algorithm][动态规划][完全背包问题][零钱兑换][零钱兑换Ⅱ][完全平方数]详细讲解

1.零钱兑换

1.题目链接

零钱兑换

2.算法原理详解

思路：
- 确定状态表示 -> dp[i][j]的含义
  - dp[i][j]：从前i个硬币中**选**，总和正好等于j，最少的硬币个数
- 推导状态转移方程：根据最后一个位置的情况，分情况讨论
  - 状态转移方程优化同[模板]完全背包
- 初始化：
  - 多开一行及一列虚拟结点
  - 由于此处状态方程求的是min，为了让不存在的情况不影响取值
    - 可以在不存在的情况初始化为无穷大，此处无穷大初始化为0x3f3f3f3f
- 确定填表顺序：从上往下，从左往右
- 确定返回值：dp[n][amount] >= INF ? -1 : dp[n][amount]
滚动数字优化同[模板]完全背包

3.代码实现

// v1.0
int coinChange(vector<int>& coins, int amount) 
{
    const int INF = 0x3f3f3f3f;

    int n = coins.size();
    vector<vector<int>> dp(n + 1, vector<int>(amount + 1));

    // Init
    for(int j = 1; j <= amount; j++)
    {
        dp[0][j] = INF;
    }

    // DP
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= amount; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= coins[i - 1])
            {
                dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        }
    }

    return dp[n][amount] >= INF ? -1 : dp[n][amount];
}
-------------------------------------------------------------------------
// v2.0 滚动数组优化
int coinChange(vector<int>& coins, int amount) 
{
    const int INF = 0x3f3f3f3f;

    int n = coins.size();
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;

    // DP
    for(int i = 1; i <= n; i++)
    {
        for(int j = coins[i - 1]; j <= amount; j++)
        {
            dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
        }
    }

    return dp[amount] >= INF ? -1 : dp[amount];
}

2.零钱兑换 II

1.题目链接

零钱兑换 II

2.算法原理详解

思路基本跟零钱兑换一致，本题代码实现就只给出滚动数组优化的版本
思路：
- 确定状态表示 -> dp[i][j]的含义
  - dp[i][j]：从前i个硬币中**选**，总和正好等于j，一共有多少种选法
- 推导状态转移方程：根据最后一个位置的情况，分情况讨论
  - 状态转移方程优化同[模板]完全背包
- 初始化：
  - 多开一行及一列虚拟结点
- 确定填表顺序：从上往下，从左往右
- 确定返回值：dp[n][amount]
滚动数字优化同[模板]完全背包

3.代码实现

int change(int amount, vector<int>& coins) 
{
    vector<int> dp(amount + 1);
    dp[0] = 1;

    for(int i = 1; i <= coins.size(); i++)
    {
        for(int j = coins[i - 1]; j <= amount; j++)
        {
            dp[j] += dp[j - coins[i - 1]];
        }
    }

    return dp[amount];
}

3.完全平方数

1.题目链接

完全平方数

2.算法原理详解

问题转化：本质就是完全背包问题
思路：
- 确定状态表示 -> dp[i][j]的含义
  - dp[i][j]：从前i个完全平方数中**选**，总和正好等于j，所有的选法中，最小的数量
- 推导状态转移方程：根据最后一个位置的情况，分情况讨论
  - 状态转移方程优化同[模板]完全背包
- 初始化：
  - 多开一行及一列虚拟结点
  - 由于此处状态方程求的是min，为了让不存在的情况不影响取值
    - 可以在不存在的情况初始化为无穷大，此处无穷大初始化为0x3f3f3f3f
- 确定填表顺序：从上往下，从左往右
- 确定返回值：dp[sqrt(n)][n]
滚动数字优化同[模板]完全背包

3.代码实现

// v1.0
int numSquares(int n) 
{
    const int INF = 0x3f3f3f3f;

    int m = sqrt(n);
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // Init
    for(int j = 1; j <= n; j++)
    {
        dp[0][j] = INF;
    }

    // DP
    for(int i = 1; i <= m; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= i * i)
            {
                dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }
        }
    }

    return dp[m][n];
}
-------------------------------------------------------------------------
// v2.0 滚动数组优化
int numSquares(int n) 
{
    const int INF = 0x3f3f3f3f;

    int m = sqrt(n);
    vector<int> dp(n + 1, INF);
    dp[0] = 0;

    // DP
    for(int i = 1; i <= m; i++)
    {
        for(int j = i * i; j <= n; j++)
        {
            dp[j] = min(dp[j], dp[j - i * i] + 1);
        }
    }

    return dp[n];
}