今日概览

今天记录了 1 道题。

题号	题目	状态	语言	标签
P1359	租用游艇	AC	Python	动态规划、最短路

刷题记录

P1359 租用游艇

• 题目：租用游艇
• 状态：AC
• 语言：Python
• 标签：动态规划、最短路

题目原文

题目描述

长江游艇俱乐部在长江上设置了 $n$ 个游艇出租站 $1,2,\dots,n$。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r_{i,j}$（$1\le i\lt j\le n$）。试设计一个算法，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

输入格式

第一行中有一个正整数 $n$，表示有 $n$ 个游艇出租站。接下来的 $n-1$ 行是一个半矩阵 $r_{i,j}$（$1\le i

输出格式

输出计算出的从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

说明/提示

$1\le n\le 200$，保证计算过程中任何时刻数值都不超过 $10^6$。

代码

n = int(input())
graph = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n):
     nlist = list(map(int,input().split()))
     j = n
     while j>i:
          num = nlist.pop()
          graph[i][j] = num
          graph[j][i] = num
          j-=1
          
memo = {}
def min_rent(graph,i):
     if i == 1:
          return 0
     if i in memo:
          return memo[i]
     rent = min(
          (min_rent(graph,j) + graph[j][i]) for j in range(1,i)
     )

     memo[i] = rent
    
     return rent

print(min_rent(graph,n))