25.3.3刷题

https://www.luogu.com.cn/problem/P1359

P1359 租用游艇

题解

简单的动态规划，a[i][j]存在下标i借到下标j还的费用，一维dp[i]数组存到下标i归还的最小花费，状态转移方程：dp[i]=min(dp[i],dp[j]+a[j][i])

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


const int N = 210;
int a[N][N];
int dp[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i < n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 2; i <= n; i++)
	{
		dp[i] = a[1][i];
	}
	
	for (int i = 3; i <= n; i++)
	{
		for (int j = 2; j < i; j++)
		{
			dp[i] = min(dp[i], dp[j] + a[j][i]);
		}
	}

	cout << dp[n];
	return 0;
}