c++ - 为什么内存比制表花费更多时间？

Question

我试图解决这个基本的硬币找零动态规划问题:

给定一个值 N，如果我们想要找 N 分钱，并且我们有无限供应每种 S = { S1, S2, .. , Sm} 值(value)的硬币，我们可以有多少种找零方式？硬币的顺序并不重要。 这是我可以创建的解决方案:

我用三种通用方法解决了这个问题。 IE。递归、DP 内存和 DP 制表。

C++ 实现:https://ideone.com/14bBIv

#include <iostream>
#include <cstring>
#include <sys/time.h>
#include <limits.h>

using namespace std;

int max2(int a, int b)
{
    return (a>b) ? a : b;
}

int max3(int a, int b, int c)
{
    if(a>c)
        return (a>b) ? a : b;
    else
        return (c>b) ? c : b;
}

int min3(int a, int b, int c)
{
    if(a<c)
        return (a<b) ? a : b;
    else
        return (c<b) ? c : b;
}


int Coins_rec(int * S, int m, int n)
{
    if(n == 0)
        return 1;

    if(n < 0)
        return 0;

    if(m<=0 && n >=0){
        return 0;
    }

    return ( Coins_rec( S, m-1, n ) + Coins_rec( S, m, n - S[m-1] ) );
}


int memo[101][101] ;


int Coins_memoization(int * S, int m, int n)
{

    if(n == 0)
        return 1;

    if(n < 0)
        return 0;

    if(m<=0 && n >=0){
        return 0;
    }

    if(memo[m][n] !=-1) {

        return memo[m][n];
    } else
    {
        memo[m][n] = ( Coins_rec( S, m-1, n ) + Coins_rec( S, m, n - S[m-1] ) );
        return memo[m][n];
    }

}


int Coins_tabulation (int * S, int m, int n)
{
    int L[m+1][n+1] ;   //L[i][j] -> Minimum number of 'i' different types of coins required to make final amonut j
    int i, j;

    L[0][0] = 1;

    for(i=0;i<=m;i++){
        for(j=0;j<=n;j++){
            if (i == 0 && j >= 0) {
                L[0][j] = 0;
            } else if (i > 0 && j == 0) {
                L[i][0] = 1;
            } else {
                L[i][j] = ( (i >= 1) ? L[i-1][j] : 0 ) + ( (j - S[i-1] >=0) ? L[i][j - S[i-1]] : 0 ) ;
            }
        }
    }
    return L[m][n];
}       // -----  end of function Coins_tabulation  ----- 




int main() {

    int arr[] = {2, 5, 3, 6};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n;

    cout << "Enter the amount" << endl;
    cin >> n;

    for(int i=0; i<=101; i++){
        for(int j=0; j<=101; j++){
            memo[i][j] = -1;
        }
    }

    struct timeval t0; gettimeofday(&t0 , NULL);

    cout << "Number of Ways = " << Coins_rec(arr, m, n) << endl;
    struct timeval t1; gettimeofday(&t1 , NULL);
    cout << "recursion : " << (t1.tv_sec - t0.tv_sec) << " seconds and " << (t1.tv_usec - t0.tv_usec) << " microseconds" << endl;

    cout << "Number of Ways (Memoization) = "  << Coins_memoization(arr, m, n) << endl;
    struct timeval t2; gettimeofday(&t2 , NULL);
    cout << "memoization : " << (t2.tv_sec - t1.tv_sec) << " seconds and " << (t2.tv_usec - t1.tv_usec) << " microseconds" << endl;


    cout << "Number of Ways (Tabulation) = "  << Coins_tabulation(arr, m, n) << endl;
    struct timeval t3; gettimeofday(&t3 , NULL);
    cout << "tabulation : " << (t3.tv_sec - t2.tv_sec) << " seconds and " << (t3.tv_usec - t2.tv_usec) << " microseconds" << endl;

    return 0;

}

。 结果如下: (通过标准输入获取的输入)

For n = 10
recursion : 0 seconds and 14 microseconds
memoization : 0 seconds and 17 microseconds
tabulation : 0 seconds and 17 microseconds

For n =100
recursion : 0 seconds and 1300 microseconds
memoization : 0 seconds and 1270 microseconds
tabulation : 0 seconds and 35 microseconds

我无法理解的是，这就是为什么对于稍大的输入，记忆化所花费的时间几乎与简单的递归解决方案相同？在这种情况下，内存是否应该比制表花费更少的时间，因为它跳过了矩阵中许多无用的计算，而这些计算在制表的情况下必须完成？

Answer 1

这是因为在内存算法的递归步骤中，您实际上是递归到 Coins_rec 而不是 Coins_memoization 。一旦你解决了这个问题，你会发现对于更大的数字来说，内存确实和制表一样快。例如，以下是我的机器上 100 的结果:

100
recursion : 0 seconds and 914 microseconds
memoization : 0 seconds and 18 microseconds
tabulation : 0 seconds and 16 microseconds