c - SPOJ COINS DP 和递归方法

Question

我最近开始解决 DP 问题，并遇到了 COINS。我尝试使用带有内存功能的 DP 来解决它，如果我使用 int 数组(我猜)，它就可以正常工作。这是我的方法(剩下一些修改):

#include <stdio.h>
#include <stdlib.h>
int dp[100000];
long long max(long x, long y)
{
   if (x > y)
      return x;
   else
      return y;
}
int main()
{
    int n,i;
    scanf("%d",&n);
    dp[0]=0;
    for(i=1;i<=n;i++)
    {
        dp[i]=max(i,dp[i/2] + dp[i/3] + dp[i/4]);
    }
    printf("%d\n",dp[n]);

    return 0;
}

但我不明白，一旦我使用 long long 数组，我就会收到 SIGSEGV。我搜索了一下，似乎有一个我不理解的递归解决方案。有人可以帮我吗？

Answer 1

限制为 n<=10e9 ，其数组大小总是会导致内存溢出，因此 SIGSEGV 。 dp 数组的类型并不重要。

您的代码中还存在其他错误。首先，有测试用例，您必须阅读它们直到 EOF。其次，由于限制是 10e9 ，您正在循环n次!当然是 TLE。

现在，对于递归解决方案，使用记忆化:

首先，将答案值保存到 10e6在数组中。将有助于节省时间。可以这样做:

long long dp[1000000] = {0};
for(int i = 1; i < 1000000; i++){
    dp[i] = max(i, dp[i/2] + dp[i/3] + dp[i/4]);
}

现在，对于任何输入 n ，求解为，

ans = coins(n);

实现coins功能为:

long long coins(long long n){
    if (n < 1000000)
        return dp[n];
    return coins(n/2) + coins(n/3) + coins(n/4);
}

Why this recursive solution works:

很明显，所有问题的答案都是n >= 12将是ans[n/2] + ans[n/3] + ans[n/4] ，所以对于n > 10e6 ，即返回。

递归的基本条件只是为了节省时间。您也可以返回0 ，但随后您将不得不处理极端情况。 (你明白我的意思了)

具体代码:

#include<stdio.h>
long long dp[1000000] = {0};

long long max(long long a, long long b){
    return a>b?a:b;
}

long long coins(long long n){
    if (n < 1000000)
        return dp[n];
    return coins(n/2) + coins(n/3) + coins(n/4);
}

int main(){
for(long long i = 1; i < 1000000; i++){
    dp[i] = max(i, dp[i/2] + dp[i/3] + dp[i/4]);
}
long long n;
while(scanf("%lld",&n) != EOF){
    printf("%lld\n", coins(n));
}
return 0;
}