动态规划--游艇租赁

package com.duoduo.day316;
/*** 游艇租赁问题* 长江上设置了n个游艇租赁站，站i到站j之间的租金是r(i,j)  计算从站1到n所需的最少租金* @author 多多*/
import java.util.Scanner;
public class Test4_5 {public static void main(String [] args) {Scanner sc=new Scanner(System.in);System.out.println("请输入站的个数n:");int n=sc.nextInt();int [][] m=new int[n+1][n+1];  //存放最少租金的数组int [][]r=new int[n+1][n+1];   //存放站点之间租金的数组int [][]s=new int[n+1][n+1];   //存放最优解的停靠站点System.out.println("请依次输入各站点之间的租金:");for(int i=1;i<=n;i++) {      for( int j=i+1;j<=n;j++) {r[i][j]=sc.nextInt();m[i][j]=r[i][j];}}rent(m,s,n);    //最少租金求解函数System.out.println("花费最少的租金为:"+m[1][n]);System.out.println("最少租金经过的站点:");System.out.print("1");print(1,n,s);   //最优解构造函数sc.close();}/*最少租金求解函数*/public static void rent(int[][] m,int[][] s,int n) {for(int d=3;d<=n;d++) {                 //将问题划分为小规模d，3个站点、4个站点...n个站点for(int i=1;i<=n-d+1;i++) {         //子问题的起点int j=i+d-1;                    //子问题的终点for(int k=i+1;k<j;k++) {        //子问题中的可停靠站点int temp=m[i][k]+m[k][j];if(temp<m[i][j]) {          //若停留站点总共的租金<直达的租金m[i][j]=temp;s[i][j]=k;              //则记录停靠点}}}}}/*打印最少租金经过站点的序列*///求得停靠点，当s[i][j]=0时说明中间没有停靠点，输出站点j，否则划分为两个子问题，继续递归public static void print(int i,int j,int[][] s) {if(s[i][j]==0) {System.out.print("-"+j);return;}print(i,s[i][j],s);print(s[i][j],j,s);}
}

时间复杂度：3层for循环 O(n的3次方）   print 函数 递归 最坏复杂度O（n)

空间复杂度： 那几个辅助数组O（n的2次方）