游艇租用问题2

 上一篇 blog 中用了一种方法来解决这个问题。在看别人博客时，发现可以用一维数组两重循环来解决。

状态转移方程 : dp (i)  = min(dp(i),dp(j)+r(j,i)) ; 其中dp(i)初始化为r(0,i), 0<j<i

code 如下:

#include <bits/stdc++.h> using namespace std;int rent[200][200] ;int getMinRenti(int n){int dp[200] ;dp[0] = 0 ;dp[1] = rent[0][1];for (int i = 2 ; i < n ;++i){dp[i] = rent[0][i] ;for (int j = 1 ; j < i ; ++j){dp[i] = min(dp[i], dp[j]+rent[j][i]);}}return dp[n-1]; } int main(){int n ;while (cin>>n){for (int i =0 ; i<n-1 ;++i){for(int j = i+1 ; j < n; ++j){cin>>rent[i][j] ;}}cout<<"minspent is "<<getMinRenti(n);}return 0; }

总结

以上是生活随笔为你收集整理的游艇租用问题2的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。