前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【每日算法Day 109】五大解法,带你深入了解完全背包方案数

【每日算法Day 109】五大解法,带你深入了解完全背包方案数

作者头像
godweiyang
发布2020-04-26 10:45:06
3460
发布2020-04-26 10:45:06
举报
文章被收录于专栏:算法码上来

今天这题是完全背包问题 + 背包问题方案数,我一共列举了 5 种解法,层层递进优化。并且从两个角度殊途同归,最终优化到同一个式子。强烈建议掌握,对理解背包问题有很大帮助。

题目链接

LeetCode 面试题 08.11. 硬币[1]

题目描述

给定数量不限的硬币,币值为 25 分、10 分、5 分和 1 分,编写代码计算 n 分有几种表示法。(结果可能会很大,你需要将结果模上 1000000007)

说明:

  • 0 <= n (总金额) <= 1000000

示例1

代码语言:javascript
复制
输入:
n = 5
输出:
2
解释:
有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2

代码语言:javascript
复制
输入:
n = 10
输出:
4
解释:
有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

题解

朴素想法(错误)

首先我们可以想到,最朴素的方法不就是组成面值 的方案数等于所有组成面值 的方案数之和,

但是这样有个很严重的问题,就是会产生重复计算,也就是将 6 = 1 + 56 = 5 + 1 视为两种情况。

动态规划 1

朴素想法的纠正方法就是,规定拆解后的数字是有序的,这样就不会出现重复计算了。

那么具体怎么实现呢?其实只需要加上一个约束,也就是强制令 为组成面值 的最大面值硬币。那么用掉它之后,组成面值 的最大面值硬币仍然只能是 ,这样转移下去就一定是有序的,不会出现面值突然增大的情况。转移方程只需要修改一下转移后的可用硬币 :

时间复杂度 ,空间复杂度 。

动态规划 2(超时)

另一条思考路线是,我们假设第 个硬币用 枚,然后枚举所有的 就行了。转移方程很好写:

但是这样时间复杂度太高了,直接超时。

时间复杂度 ,空间复杂度 。

转移方程优化

神奇的地方来了,上面两种方法,全部可以优化为同一个式子,仔细看好了。

空间优化

注意到,上面转移方程每个时刻 其实只和 还有 时刻有关,所以可以把第一个维度消除掉。这样转移方程就变为了:

但是需要特别注意的是,这里一共有三项,分别表示的是第 时刻、第 时刻、第 时刻。所以在两层循环遍历的时候,第一层循环必须是遍历硬币 ,第二层才是遍历组成的面值 ,这样才不会导致第 时刻的值被覆盖掉无法访问。

数学法

代码

动态规划 1(c++)

代码语言:javascript
复制
class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    static const int N = 1000010;
    static const int M = 4;

    ll dp[M][N];
    int p[M] = {1, 5, 10, 25};

    int waysToChange(int n) {
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < M; ++i) dp[i][0] = 1;
        for (int i = 0; i < M; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 0; k <= i; ++k) {
                    if (j >= p[k]) {
                        (dp[i][j] += dp[k][j-p[k]]) %= mod;
                    }
                }
            }
        }
        return dp[M-1][n];
    }
};

动态规划 2(超时)(c++)

代码语言:javascript
复制
class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    static const int N = 1000010;
    static const int M = 4;

    ll dp[M][N];
    int p[M] = {1, 5, 10, 25};

    int waysToChange(int n) {
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < M; ++i) dp[i][0] = 1;
        for (int i = 0; i <= n/p[0]; ++i) dp[0][i*p[0]] = 1;
        for (int i = 1; i < M; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 0; k <= j/p[i]; ++k) {
                    (dp[i][j] += dp[i-1][j-k*p[i]]) %= mod;
                }
            }
        }
        return dp[M-1][n];
    }
};

转移方程优化(c++)

代码语言:javascript
复制
class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    static const int N = 1000010;
    static const int M = 4;

    ll dp[M][N];
    int p[M] = {1, 5, 10, 25};

    int waysToChange(int n) {
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < M; ++i) dp[i][0] = 1;
        for (int i = 0; i <= n/p[0]; ++i) dp[0][i*p[0]] = 1;
        for (int i = 1; i < M; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = dp[i-1][j];
                if (j >= p[i]) (dp[i][j] += dp[i][j-p[i]]) %= mod;
            }
        }
        return dp[M-1][n];
    }
};

空间优化(c++)

代码语言:javascript
复制
class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    static const int N = 1000010;
    static const int M = 4;

    ll dp[N];
    int p[M] = {1, 5, 10, 25};

    int waysToChange(int n) {
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for (int j = 0; j < M; ++j) {
            for (int i = 1; i <= n; ++i) {
                if (i >= p[j]) {
                    (dp[i] += dp[i-p[j]]) %= mod;
                }
            }
        }
        return dp[n];
    }
};

数学法(c++)

代码语言:javascript
复制
class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;

    int waysToChange(int n) {
        ll res = 0;
        for (int i = 0; i <= n/25; ++i) {
            ll r = n - 25 * i;
            ll x = r / 10, y = r / 5;
            (res += (x + 1) * (y - x + 1)) %= mod;
        }
        return res;
    }
};

参考资料

[1]

LeetCode 面试题 08.11. 硬币: https://leetcode-cn.com/problems/coin-lcci/

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-04-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法码上来 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目链接
  • 题目描述
  • 题解
    • 朴素想法(错误)
      • 动态规划 1
        • 动态规划 2(超时)
          • 转移方程优化
            • 空间优化
              • 数学法
              • 代码
                • 动态规划 1(c++)
                  • 动态规划 2(超时)(c++)
                    • 转移方程优化(c++)
                      • 空间优化(c++)
                        • 数学法(c++)
                          • 参考资料
                          领券
                          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档