算法概论实验五

算法概论实验

实验五
实验目的与要求：掌握动态规划方法的基本思想与设计策略。
1．最长递增子序列问题
【问题描述】
给定一个整数数组，设计一个动态规划算法求出该数组中的最长递增子序列。
2．矩阵连乘问题
【问题描述】
给定n个矩阵{A1，A2，…,An},其中AiAi+1是可乘的，i=1，2，…，n-1,考察这n个矩阵的连乘积A1A2…An，设计一个动态规划算法，求出这个矩阵连乘积问题的最优计算顺序。
实现要求：随机生成n个合法的可连乘的矩阵，以完全加括号的方式输出其最优计算顺序。

LIS Question

// test5.1.cpp : 
// 1．最长递增子序列问题
//【问题描述】
//给定一个整数数组，设计一个动态规划算法求出该数组中的最长递增子序列。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
// 输出LIS  序列
void outputLIS(int * arr, int index, int lis, int *L)
{
    //终止条件
    if (lis == 0 || index < 0)
        return;
    //找到第一个L[index]==lis
    while (L[index]!=lis && index>0)
        index--;
    //反序输出
    if (index >= 0  && L[index]==lis)
    {
        outputLIS(arr, index - 1, lis - 1, L);
        cout << arr[index] << ",";
    }
}
int LIS(int *a, int n)
{
    //定义一个存取结果的数组
    int *L = new int[n];
    //填写次序 0 to n-1
    for (int j = 0; j < n;j++)
    {
        L[j] = 1;//BaseCase
        //find max L[i]
        for (int i = 0; i < j;i++)
        {
            if (a[i]<a[j] && L[i]+1 > L[j])
            {
                L[j] = L[i] + 1;
            }
        }
    }
    //return the max of L[0~n-1]
    int max = L[0];
    for (int i = 0; i < n; i++)
    {
        //cout << L[i] << "  ";
        if (L[i]>max)
        {
            max = L[i];
        }
    }
    //回溯输出
    cout << "LIS如下：";
    outputLIS(a, n,max, L);
    return max;
}
int main()
{
    int a[] = { 5, 2, 8, 6, 3, 6, 9, 7, };
    int n = sizeof(a) / sizeof(int);
    cout<<endl<<"长度为：" << LIS(a, n) << endl;
    return 0;
}