入门DP | 2：租用游艇问题

￡神魔★判官ぃ 2023-05-28 11:15 22阅读 0赞

## 租用游艇问题 ##

问题描述: 长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n. 游客可在这些游艇出租站租用游艇, 并在下游的任何一个游艇出租站归还游艇. 游艇出租站i到出租站j之间的租金为r(i,j), 1<=i<j<=n. 试设计一个算法, 计算出从游艇出租站1到游艇出租站n所需的最少租金, 并分析算法的计算复杂性.

算法设计: 对于给定的游艇出租站i到游艇出租站j的租金r(i,j), 1<=i<j<=n. 计算出租站1到n所需的最少租金.

数据输入: 第1行有一个正整数n, n<=200, 表示有n个游艇出租站. 接下来n-1行是r(i,j), 1<=i<j<=n.

结果输出: 游艇出租站1到n最少租金.

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入</th> 
   <th>期待的输出</th> 
   <th>时间限制</th> 
   <th>内存限制</th> 
   <th>额外进程</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td>&nbsp; 
    <ol> 
     <li>3↵</li> 
     <li>5&nbsp;15↵</li> 
     <li>7↵</li> 
    </ol></td> 
   <td>&nbsp; 
    <ol> 
     <li>12↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

--------------------

本题可以说是[区间DP | 1：矩阵链乘问题（含优化） —— 例题：矩阵链乘、合并石子][DP _ 1_ _]的一个小小部分（看完这一题再去看链接就豁然开朗~）。不过我是A完了那一题再来些这个的，就是一个入门级的DP，小菜一碟啦~

**处理输入**

一个有n个节点组成的线段，给出了任意两不同节点之间的收费r。对节点分别编号为 1..n，可以用二维数组 r\[ i \]\[ j \] 表示节点 i 到节点 j 的收费r。

**动态分析**

其实对于一个长度为 l 的线段 r\[ i \]\[ j \] (其中有j = i + l)，它可以由两段长度小于 l 的子线段组成，且若要原线段是最优解（花费为最小值），其两个子线段也应该是最优解。故此模型满足**最优子结构**的性质，且容易看出，很多子结构是重叠的，此模型又具备**重叠子问题**的性质。故，本题采用动态规划求解啦~

**模型建立**

采用一个二维数组 dp\[ i \]\[ j \] 记录节点 i 到节点 j 的最优解（最小收费r）。根据上面对最优子结构分析，我们应该先求出子问题的最优解再推断出原问题的最优解，故可以使用**自底向上**的方法来实现。先从 l = 2 开始分析，依次上推到 l = n即得到答案 dp\[1\]\[n\]。状态转移方程如下：

![dp\[i\]\[j\] = min\_\{i< k< j\}(dp\[i\]\[k\]+dp\[k\]\[j\])][dp_i_j_ _ min_i_ k_ j_dp_i_k_dp_k_j]

不要忽略了节点  i 到节点 j 不划分子问题的情况，直接取r\[ i \]\[ j \]。为方便起见，我们将dp\[ i \]\[ j \]先赋值为r\[ i \]\[ j \]即可，之后在比较的过程中会选取最小的。

--------------------

完整AC代码

#include <cstdio>
    #include <algorithm>
    
    #define MAXN 205
    using namespace std;
    
    int main() {
        int n, r[MAXN][MAXN], dp[MAXN][MAXN];
        scanf("%d", &n);
    
        /* 处理输入 */
        for (int i = 1; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                scanf("%d", &r[i][j]);
    
        /* 自底向上求解 */
        for (int l = 1; l < n; l++) {  //长度l:1..n
            for (int i = 1; i <= n - l; i++) {  //遍历所有长度为l的情况
                int j = i + l;  
                dp[i][j] = r[i][j];  //赋予初值（不断开的情况）
                for (int k = i + 1; k < j; k++)  //寻找中间点断开，更新最优的
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
        printf("%d\n", dp[1][n]);
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

--------------------

**有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ **

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]

[DP _ 1_ _]: https://blog.csdn.net/weixin_43787043/article/details/104965598
[dp_i_j_ _ min_i_ k_ j_dp_i_k_dp_k_j]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Bi%5D%5Bj%5D%20%3D%20min_%7Bi%3C%20k%3C%20j%7D%28dp%5Bi%5D%5Bk%5D&plus;dp%5Bk%5D%5Bj%5D%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/80edda64170b4700862606877fd14d4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20230528/58d65c914f9e43289316b72df4e2d299.png