递归法解题思路

#include<iostream>
using namespace std;
int dp[10000]={0},a[11];
//数组dp表示公里数为下标的车费最便宜价格
//数组a用来容纳走下标公里所需要的车费
int price(int dis){
    //递归方法解题
    if(dp[dis]!=0)return dp[dis];//dp[dis]==0表示dis公里最便宜车费没有算过
    //算过一次，就不需要算第二次了
    int mint = dis*a[1];//mint表示最便宜车费的价格
    for(int i=1;i<=min(10,dis);i++){
        if(mint>price(dis-i)+a[i])//i表示是否需要一次性乘坐i公里
            mint=price(dis-i)+a[i];//如果一次性乘坐i公里比原价便宜，乘坐i公里
    }
    dp[dis]=mint;
    return mint;
}
int main(){
    int n;
    for(int i=1;i<=10;i++)
        cin >> a[i];
    cin>>n;
    cout<<price(n);
    
    return 0;
}