[数据结构与算法]动态规划——例题

动态规划解题思路：
总共分为四步：
1 建立一个新的一维数组或二维数组，根据题意即给出的变量来决定建立的数组类型。
2若是一维数组，确定数组第一个元素的取值。
若是二维数组，则确定数组第一行和第一列的值。
3找出状态转换方程式。
4返回结果。
例题1：求最大不连续子序列
设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
思路： 首先设置一个数组temp[i]用来存储到i的最长子序列。其次，初始化temp[i]={1},然后找出状态转换方程式：如果for(j=1;j<i;j++) 当arr[i]>arr[j]时，temp[i]=max(temp[i],temp[j]+1)当arr[i]<arr[j]，则temp[i]不更新

#include <iostream>
#include <bits/stdc++.h>
#include <string>

using namespace std;
//测试数据
/*
4
2 1 3 50
*/
//  {2,3,50} 测试结果：3

//最长非连续子序列问题
int main()
{
    int n;
    int arr[101]; //定义数组存储序列
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    int temp[101]; //动态规划的第一步建立的一维数组
   for(int i=1;i<=n;i++) //对元素初始化
    temp[i]=1;
    for(int i=2;i<=n;i++)    //状态转换
    {
        for(int j=1;j<i;j++)
        {
            if(arr[i]>arr[j])
            {
                temp[i]=max(temp[i],temp[j]+1);

            }
        }
    }
    //求出temp数组的最大值
    int maxt=0;
    for(int i=1;i<=n;i++)
    {
        if(maxt<temp[i])
        {

            maxt=temp[i];
        }
    }
    cout<<maxt<<endl;
    return 0;
}

例题2：求连续最大子序列之和
给定一个整数数组 arr[] ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和.
思路：先设置一个数组temp[i]用来存储和;temp[1]初始化为arr[1];当temp[i-1]+arr[i]>arr[i],temp=temp[i-1]+arr[i],否则temp[i]=arr[i];
代码：

#include <iostream>
#include <bits/stdc++.h>
#include <string>

using namespace std;

/*测试数据
输入 ：9
-2 1 -3 4 -1 2 1 -5 4

输出：6

解释：连续子序列{4 -1 2 1}和最大，为6
*/

//最大子序列和

int main()
{

    int n;
    int arr[101];  //存储原始数组
    int temp[101]; //存储和
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    temp[1]=arr[1]; //初始化
    for(int i=2;i<=n;i++)   //状态转换
    {

        if(temp[i-1]+arr[i]>arr[i])
            temp[i]=temp[i-1]+arr[i];
        else
            temp[i]=arr[i];
    }
    //求temp[]数组最大值
    int maxand=temp[1];
    for(int i=2;i<=n;i++)
    {
        if(temp[i]>maxand)
            maxand=temp[i];
    }
    cout<<maxand<<endl;
    return 0;

}

例题3：两个字符串最大公共子序列
给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB
则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA
思路：设置一个二维数组dp[i][j]来表示坐标（i,j）时的最长子序列。初始化第一行和一列，如果x[i]=y[j],则dp[i][j]=dp[i-1][y-1]+1;
否则的话，dp[i][j]=max(dp[i-1][j]，dp[i][j-1]);
代码：

#include <iostream>
#include <bits/stdc++.h>
#include <string>

using namespace std;

//最大公共子序列
int main()
{
    string x;
    string y;
    cin>>x;
    cin>>y;
    int dp[21][21];
    int len1=x.length();
    int len2=y.length();
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=len1;i++)
    {

        for(int j=1;j<=len2;j++)
        {
           if(x[i-1]==y[j-1])
           {
               dp[i][j]=dp[i-1][j-1]+1;
           }
           else
           {

               dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
           }
        }
    }
    cout<<dp[len1][len2]<<endl;
    int k=0;
    char temp[101];
    int p=len1-1;
    int q=len2-1;
    while(p>=0&&q>=0)
    {

        if(dp[p+1][q+1]==dp[p][q]+1&&x[p]==y[q])
        {
            temp[k++]=x[p];
            p--;
            q--;
        }
        else if(dp[p+1][q+1]==dp[p][q+1])
        {
            p--;
        }
        else
        {
            q--;
        }
    }
    for(int i=k-1;i>=0;i--)
    {
        cout<<temp[i]<<" "<<endl;
    }
    return 0;

}

例题4：找零钱问题
问题描述：
现存在一堆面值为 1,2,5,11,20,50 面值的硬币，问最少需要多少个硬币才能找出总值为 N个单位的零钱
思路：创建一个二维数组纵坐标表示硬币的面值，横坐标表示还需要找j个单位的零钱。初始化第一行第一列.对于每一种硬币，若使用这种硬币则dp[i][j]=dp[i][j-arr[i]]+dp[i-1][j],否则dp[i][j]=dp[i-1][j];
代码：

#include <iostream>
#include <bits/stdc++.h>
#include <string>

using namespace std;
/*测试样例
3
1 3 4
4
*/
// 输出：3

//找零钱问题

/*
第一行 输入面值的张数n
第二行 输入面值arr[]
第三行 输入应找的零钱数
*/
int main()
{

    int n;
    int p;
    int arr[101];
    int dp[21][21];
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>arr[i];
    }
    cin>>p;
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        dp[i][0]=1;
    }
    for(int i=0; i<=p; i++)
    {
        if(i%arr[1]==0)
            dp[1][i]=1;
        else
            dp[1][i]=0;
    }
    for(int i=2; i<=n; i++)
    {
        for(int j=1; j<=p; j++)
        {

            if(j>=arr[i])
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-arr[i]];
            }
            else
            {

                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<<dp[n][p]<<endl;
    return 0;

}