记忆化搜索

解题思路:自顶而下搜索最小值

注意事项:记录答案防止时间爆炸

参考代码:

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long i64;

typedef int i32;

typedef long double ld;

i64 dp[1200];

int a[11];

i64 like(int n)

{

    if(n==0)

        return 0; //搜索结束边界

    if(n<0)

        return 9999999999999; //小于0返回正无穷

    if(dp[n]<12345643)

        return dp[n];   //搜过了就不用再搜索了

    for(int i=1;i<=10;i++)

        dp[n]=min(dp[n],like(n-i)+a[i]); //比较

    return dp[n];

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    memset(dp,0xf,sizeof(dp)); //初始化为极大值

    for(int i=1;i<=10;i++)

        cin>>a[i];

    int n;

    cin>>n;

    cout<<like(n);

return 0;

}