动态规划c++

解题思路:求出每一段路的最优情况，然后求得最小值

参考代码:

#include <iostream>
#include <algorithm> 
using namespace std;
int main(){
	int value[11], dp[11];
	int dis;
	for(int i = 1; i < 11; i++) cin >>value[i];
	cin>>dis;
	dp[1] = value[1], dp[0] = 0;
	for(int i = 2; i < 11; i++) {
		int minn = value[i];
		for(int j = i - 1; j >= i / 2; j--) {
			minn = min(minn,dp[j]+dp[i-j]);
		}
		dp[i] = minn;//该段路程的最少费用
	}
	int res = dis/10*dp[10] + dp[dis%10];
	for(int i = 1; i < 10; i++)
		res = min(res, dp[i]*(dis/i)+dp[dis%i]);
	cout << res <<endl;
	return 0;
}