给定数组arr,arr中所有的值都为正整数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给 定一个aim,代表要找的钱数,求组成aim的最少货币张数。 如果无解,请返回-1.
时间: 2023-02-08 21:39:16 浏览: 101
给定数组arr,其中arr中所有的值都是正整数且不重复,代表不同面值的纸币或硬币。给定aim,代表要找的钱数。求组成aim的最少货币张数。如果无解,则返回-1.
这个问题可以使用动态规划解决,具体过程为:
1. 创建一个表格dp,其中dp[i]表示组成i元所需最少货币数。
2. 初始化dp数组,将所有元素设为无穷大,dp[0]设为0。
3. 从1到aim遍历每一个钱数,对于每一种面值的货币,更新dp数组中对应钱数所需最少货币数。
4. 返回dp[aim],如果 dp[aim] == 无穷大 ,则代表无解,返回-1
code example:
```python
def coin_change(arr,aim):
n = len(arr)
dp = [float("inf")]*(aim + 1)
dp[0] = 0
for i in range(1,aim + 1):
for j in range(n):
if i - arr[j] >= 0:
dp[i] = min(dp[i],dp[i - arr[j]] + 1)
return -1 if dp[aim] == float("inf") else dp[aim]
```
相关问题
给定数组arr,arr中所有的值都为正整数且不重复。每个值代表一种面值的货币,每种货币的面值可以使用任意张,再给定一个aim,代表要找的钱数,求组成aim的最少货币数。如果无解,请返回1
这是一道经典的动态规划问题,可以使用动态规划算法解决。我们定义一个一维数组dp,其中dp[i]表示组成钱数i所需的最少货币数。初始时,将dp[0]赋值为0,其余元素赋值为正无穷大。然后,对于每个面值v,遍历数组dp,更新dp[j] = min(dp[j], dp[j-v]+1),其中j>=v。
如果dp[aim]的值仍然是正无穷大,则代表无解,返回1;否则,返回dp[aim]即可。
笑话:为什么小明的作业总是交不完?因为他总是做到一半就去睡觉了。
c语言写输出给定数组中每相邻两个元素平均值的平方根之和
好的,这个问题可以回答。以下是C语言的代码实现:
```
#include <stdio.h>
#include <math.h>
int main() {
double arr[] = {3, 6, 2, 8}; // 给定数组
int len = sizeof(arr) / sizeof(arr[0]); // 数组长度
double sum = 0; // 用于存储和
for (int i = 0; i < len - 1; i++) {
double avg = (arr[i] + arr[i+1]) / 2; // 相邻两个元素的平均值
double sqrt_avg = sqrt(avg); // 平均值的平方根
sum += sqrt_avg;
}
printf("结果为:%.2f", sum); // 保留两位小数输出
return 0;
}
```
希望对你有所帮助。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)