迭代方法似乎比递归实现（硬币找零）慢

Question

#include <cstdio>


using namespace std;

#define garbaze 0
//number of ways changes can be made
int coins[] = {garbaze,50,25,10,5,1}; //order does not matter//as         in         the     //count_ways... function we are returning
//0 if which_coin_now is <= 0 so it
//does n't matter what we have in the index 0 [garbaze] .. but we must put //something there to implement the
//code using the pseudo code or recursive relation
typedef unsigned long long ull; //simple typedef
ull dp[7490][6]; //2d table
//recursive approach


ull count_ways_of_changes(int money_now,int which_coin_now)
{
    if(money_now == 0)
        return 1;
    if(money_now < 0 || which_coin_now <=0 )
        return 0;
    if(dp[money_now][which_coin_now] == -1)
        dp[money_now][which_coin_now] = count_ways_of_changes(money_now,which_coin_now-1) //excluding current coin
        + count_ways_of_changes(money_now - coins[which_coin_now],which_coin_now) ; //including current coin


    return dp[money_now][which_coin_now] ;


}

int main()
{
    for(int loop = 0; loop< 7490 ;loop++)
        for(int sec_loop = 0;sec_loop<6;sec_loop++)
                 dp[loop][sec_loop] = -1; //table initialization
int N = 0;
while(scanf("%d",&N)==1)
{
    printf("%llu\n",count_ways_of_changes(N,5)); //llu for unsigned long long
}
return 0;
}

这个被接受了（用了 0.024 秒）

我的迭代方法：

#include <cstdio>
//#include <iostream>
//using namespace std;
typedef unsigned long long ull;
ull dp[7490][6];
#define garbaze 0
int value_coins[] = {garbaze,5,1,10,25,50} ;
inline ull count_ways_change(int money,int num_of_coins)
{
    for(int sum_money_now = 0; sum_money_now <= money ;sum_money_now++)
        for(int recent_coin_index = 0 ; recent_coin_index <= num_of_coins ; recent_coin_index++)
//common mistakes : starting the second index at num_of_coins and decrementing till 0 ...see we are pre calculating
//we have to start bottom to up....if we start at dp[0][5] .....to dp[1][5] but to know that i need to know
//dp[1][4] and dp[..][5] before hand ..but we have not calculated dp[1][4] yet...in this case i don't go to infinite
//loop or anything as the loop is well defined but i get stupid garbaze answer

    {
        if(sum_money_now == 0)
            dp[sum_money_now][recent_coin_index] = 1;
        else if(recent_coin_index == 0)
            dp[sum_money_now][recent_coin_index] = 0;
        else if(sum_money_now < value_coins[recent_coin_index] && recent_coin_index != 0)
            dp[sum_money_now][recent_coin_index] = dp[sum_money_now][recent_coin_index-1] ;
            else
                dp[sum_money_now][recent_coin_index] = dp[sum_money_now][recent_coin_index-1] + dp[sum_money_now - value_coins[recent_coin_index] ][recent_coin_index] ;
 //   cout<<dp[sum_money_now][recent_coin_index]<<endl;
    }


    return dp[money][num_of_coins] ;
}
int main()
{/*
    for(int loop = 0; loop< 7490 ;loop++)
        for(int sec_loop = 0;sec_loop<6;sec_loop++)
                 dp[loop][sec_loop] = -1; //table initialization

*/ //In the iterative version do not need to initialize the table as we are working bottom - up
int N = 0;
while(scanf("%d",&N)==1)
{

printf("%llu\n",count_ways_change(N,5)); //llu for unsigned long long

}
return 0;
}

但是我超过了时间限制 one.It 给出了正确的输出，但我不明白为什么这个必须这么慢？

Answer 1

不同之处在于您的递归解决方案会记住先前任务的部分解决方案（因为 DP table 是全局的并且不会在不同输入之间被删除），而迭代不会 - 对于每个新输入，它从头开始重新计算 DP 矩阵。

可以通过记住 DP table 的哪一部分已经计算并避免重新计算来解决，而不是每次查询都从头开始重新计算。

迭代方法似乎比递归实现（硬币找零）慢

Iterative approach seems slower than recursive implemetation(coin change)

c++

algorithm

recursion

dynamic-programming

coin-change