动态规划C++实现--换钱的方法数（一）（暴力递归和记忆化搜索）

程序员文章站 2022-05-12 16:12:30

...

题目：换钱的方法数

给定数组 arr, arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。

将原文的伪代码进行C++实现

程序员代码面试指南第四章递归和动态规划 点击打开链接

例1：arr = [5, 10, 25, 1] ,aim = 15， 6种方法

1) 3张5元； 2）1张10元+1张5元； 3）1张10元+5张1元； 4）10张1元+1张5元；5）2张5元+5张1元； 6）15张1元

1、暴力递归

(1) 用0张5元，[10,25,1]组成1000

(2) 用1张5元，[10,25,1]组成995

......

(3)用200张5元，[10,25,1]组成0

使用递归函数进行求解。时间复杂度较高，且与arr中钱的面值有关，最差情况为O（aim^N）

代码如下：

输入：第一行：钱面值的数量N 钱数aim

第二行：钱的面值arr矩阵

4 15

5 10 25 1

输出：方法数

#include <bits/stdc++.h>
using namespace std;
int process1(int arr[], int index, int aim);
int coins1(int arr[],int aim);

int main(){
    int N, aim; cin >> N >> aim;
    int arr[N];
    for (int i = 0; i < N; i++){
        cin >> arr[i];
    }
    cout << coins1(arr, aim)<< endl;
    return 0;
}

int coins1(int arr[],int aim){
    if (arr == NULL || aim < 0){
        return 0;
    }
    return process1(arr, 0, aim);
}

int process1(int arr[], int index, int aim){
    int res = 0;
    if (index == sizeof(arr)){   //当指针指向数组的末尾，
        res = (aim ==0)? 1 : 0;  // 目标值被恰好分完，此时计数1
    }else {
        for(int i = 0; arr[index] * i <= aim; i++) {
            res += process1(arr, index+1, aim - arr[index] * i);
        }
    }
    return res;
}

2、记忆化搜索

暴力递归复杂度很高的原因在于每一个递归的过程都没被记录下来。可以采用空间换时间的方式，将前面计算得到结果记录到数组中，这里将计算结果记录到数组map中，当下次进行同样的递归过程之前，现在map中查询，如果计算过，取值使用，否则进入递归中。

map[i][j] = 0; 表示未计算。 map[i][j] = -1; 表示计算过，但返回值为0。 map[i][j] 不为0 且不为 -1，记为a.

记忆化搜索方法的时间复杂度为O（N*aim^2）

代码如下：

// 换钱的方法数 <记忆化搜索> <复杂度0(N*aim^2)>
// 空间换时间
#include <bits/stdc++.h>
using namespace std;
int process2(int arr[], int index, int aim, int map1[][10001]);
int coins2(int arr[],int aim);

int main(){
    int N, aim; cin >> N >> aim;
    int arr[N];
    for (int i = 0; i < N; i++){
        cin >> arr[i];
    }
    cout << coins2(arr, aim)<< endl;
    return 0;
}

int coins2(int arr[],int aim){
    if (arr == NULL || aim < 0){
        return 0;
    }
    int map1[sizeof(arr) + 1][10001];
    return process2(arr, 0, aim, map1);

}

int process2(int arr[], int index, int aim, int map1[][10001]){
    int res = 0;
    if (index == sizeof(arr)){   //当指针指向数组的末尾，
        res = (aim ==0)? 1 : 0;  // 目标值被恰好分完，此时计数1
    }else {
        int mapvalue = 0;
        for(int i = 0; arr[index] * i <= aim; i++) {
            mapvalue = map1[index + 1][aim - arr[index] * i];
            if (mapvalue != 0){
                res += mapvalue == -1 ? 0 : mapvalue;
            } else{
                res += process2(arr, index+1, aim - arr[index] * i, map1);
            }
        }
    }
    map1[index][aim] = res == 0 ? -1 : 0;
    return res;
}

动态规划C++实现--换钱的方法数（一）（暴力递归和记忆化搜索）