c++ - 动态规划 - 原始计算器

Question

问题的完整解释在这里--- http://imgur.com/a/UiE7L。我已经编写了代码，但它显示了我无法解决的分段错误。根据程序的逻辑，我保存了在数组的第 n 个位置上达到第 n 个所需的最少操作数。我打算按照这个逻辑。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>

long long f(long long n, vector <long long> arr)
{ 
    arr[1]=0;

    arr.push_back(n);
    long long ans=0, ret=0;

    if (n==1)
    {
        return (0);
    }
    ans= f(n-1, arr) + 1;


    if (n%2==0)
    {
        ret= f(n/2, arr) + 1;
        if (ret<ans)
        {
            ans=ret;
            std::cout<<ans<<'\n';
        }
    }
    if (n%3==0)
    { 
        ret= f(n/3, arr) + 1;
        if (ret<ans)
        {
            ans=ret;
            std::cout<<ans<<'\n';
        }
    }
    arr[n]=ans;

    return arr[n];    
}

int main() {

    long long n;
    std::cin >> n;
    std::vector<long long> arr;
    std::cout<<f(n, arr);

    return 0;
}

标签： c++algorithmdynamic-programming

Answer 1

#include <bits/stdc++.h>
using namespace std;

long long f(long long n, vector <long long> arr)
{ 
    arr[1]=0;

    //arr.push_back(n);       // not required
    long long ans=0, ret=0;

    if (n==1)
    {
        return (0);
    }
    ans= f(n-1, arr) + 1;


    if (n%2==0)
    {
        ret= f(n/2, arr) + 1;
        if (ret<ans)
        {
            ans=ret;
            //std::cout<<ans<<'\n';
        }
    }
    if (n%3==0)
    { 
        ret= f(n/3, arr) + 1;
        if (ret<ans)
        {
            ans=ret;
            //std::cout<<ans<<'\n';
        }
    }
    arr[n]=ans;

    return arr[n];    
}

int main() {

    long long n = 120;
    std::vector<long long> arr(n+1);     // declare arr with size n+1 
    std::cout<<f(n, arr);

    return 0;
}

您已经访问了 a[1] 而没有声明数组的大小 >= 2，因为 c++ 中的数组是 0 索引，此外，如果您arr(n+1)在声明时提供了一些初始大小的数组，则无需再次推入 n 的值arr。

那么您的解决方案可以正常工作。

对于迭代方法

#include <bits/stdc++.h>
using namespace std;

int main() {

    long long n;
    cin >> n;
    vector<long long> arr(n+1);

    for (int i = 1; i <= n; i++) {
        arr[i] = arr[i - 1] + 1;
        if (i % 2 == 0) arr[i] = min(1 + arr[i / 2], arr[i]);
        if (i % 3 == 0) arr[i] = min(1 + arr[i / 3], arr[i]);
    }
    cout << arr[n]-1 << endl;
    return 0;
}