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

题目链接

LeetCode 面试题 08.11. 硬币[1]

题目描述

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

输入：
n = 5

2

5=5
5=1+1+1+1+1

输入：
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

代码

动态规划 1（c++）

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++）

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++）

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];
}
};

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++）

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月前
|

【数学】【排序】【C++算法】3027人员站位的方案数
【数学】【排序】【C++算法】3027人员站位的方案数
31 0
|
1月前
|

|
1月前
|

python 算法 两数之和 的多种解法
python 算法 两数之和 的多种解法
53 0
|
1月前
|

43 0
|
12天前
|

Redis集群,集群的概念 三种主流分片方式1.哈希求余 一致性哈希算法:方案三:哈希槽分区算法问题一Redis集群是最多有16384个分片吗问题二:为什么是16384个,集群扩容:1.新的主节点
Redis集群,集群的概念 三种主流分片方式1.哈希求余 一致性哈希算法:方案三:哈希槽分区算法问题一Redis集群是最多有16384个分片吗问题二:为什么是16384个,集群扩容:1.新的主节点
34 1
|
1月前
|

22 0
|
1月前
|

24 0
|
1月前
|

75 1
|
1月前
|

CodeFuse成功支持通义千问算法大赛，评测方案已开源

93 1
|
1月前
|

python 算法 两数相加多种解法
python 算法 两数相加多种解法
84 0