这是本系列的第二篇文章，旨在记录我学习C++历程中所有的感想和感悟。

DP-TR-1 冬冬爬楼梯

题目信息

题目描述：

冬冬爬楼梯，一步可以1级，也可以爬2级、3级。冬冬很可爱，每到一处楼梯处，他都想知道直完这个楼梯有多少种走法。但由于有的时候楼梯级数太多，可能是个天文数字，很显然，对于还处于小学5年级的冬冬是不太现实的。聪明的你，能帮冬冬实现这个愿望吗？

输入

多组测试数据，每组测试数据一行一个整数()

输出

对于每组测试数据，输出一个整数，为级楼梯冬冬走完的方法数。

样例输入

1
2
3

样例输出

1
2
4

数据范围

对于 的数据，满足;

对于的数据，满足.

题目分析

经典的递推方法推导，为动态规划的思路鼻祖。记表示登上阶台阶的方法总数，则对于阶台阶有不重复的三种登上方法，分别是第一步走一阶后再走和第二步走两阶后再走以及第三步走三阶后再走.

唯一的问题在于数据范围需要高精度······（您确定这玩意儿该放在第一题······）

代码

#include<bits/stdc++.h>
using namespace std;
class MyInteger
{
private:
    string bignum;
    struct calcpro
    {
        // compare比较函数：相等返回0，大于返回1，小于返回-1
        int compare(string str1, string str2)
        {
            if (str1.length() > str2.length())
                return 1;
            else if (str1.length() < str2.length())
                return -1;
            else
                return str1.compare(str2);
        }
        //高精度加法
        //只能是两个正数相加
        string add(string str1, string str2) //高精度加法
        {
            string str;
            int len1 = str1.length();
            int len2 = str2.length();
            //前面补0，弄成长度相同
            if (len1 < len2)
            {
                for (int i = 1; i <= len2 - len1; i++)
                    str1 = "0" + str1;
            }
            else
            {
                for (int i = 1; i <= len1 - len2; i++)
                    str2 = "0" + str2;
            }
            len1 = str1.length();
            int cf = 0;
            int temp;
            for (int i = len1 - 1; i >= 0; i--)
            {
                temp = str1[i] - '0' + str2[i] - '0' + cf; //逐位计算,A+B+进位
                cf = temp / 10;                            //该位计算进位确认
                temp %= 10;                                //该位计算结果确认
                str = char(temp + '0') + str;              //该位计算结果存储
            }
            if (cf != 0)
                str = char(cf + '0') + str;
            return str;
        }
        //高精度减法
        //只能是两个正数相减，而且要大减小
        string sub(string str1, string str2) //高精度减法
        {

            string str;
            int tmp = str1.length() - str2.length();
            int cf = 0;
            for (int i = str2.length() - 1; i >= 0; i--)
            {
                if (str1[tmp + i] < str2[i] + cf)
                {
                    str = char(str1[tmp + i] - str2[i] - cf + '0' + 10) + str;
                    cf = 1;
                }
                else
                {
                    str = char(str1[tmp + i] - str2[i] - cf + '0') + str;
                    cf = 0;
                }
            }
            for (int i = tmp - 1; i >= 0; i--)
            {
                if (str1[i] - cf >= '0')
                {
                    str = char(str1[i] - cf) + str;
                    cf = 0;
                }
                else
                {
                    str = char(str1[i] - cf + 10) + str;
                    cf = 1;
                }
            }
            str.erase(0, str.find_first_not_of('0')); //去除结果中多余的前导0
            return str;
        }
        //高精度乘法
        //只能是两个正数相乘
        //速度更慢，因为涉及了高精度加法的调用
        string mul(string str1, string str2)
        {
            string str;
            int len1 = str1.length();
            int len2 = str2.length();
            string tempstr;
             
            for (int i = len2 - 1; i >= 0; i--)
            {
                tempstr = "";
                int temp = str2[i] - '0';
                int t = 0;
                int cf = 0;
                if (temp != 0)
                {
                    for (int j = 1; j <= len2 - 1 - i; j++)
                        tempstr += "0";
                    for (int j = len1 - 1; j >= 0; j--)
                    {
                        t = (temp * (str1[j] - '0') + cf) % 10;
                        cf = (temp * (str1[j] - '0') + cf) / 10;
                        tempstr = char(t + '0') + tempstr;
                    }
                    if (cf != 0)
                        tempstr = char(cf + '0') + tempstr;
                }
                str = add(str, tempstr);
            }
            str.erase(0, str.find_first_not_of('0'));
            return str;
        }
        //高精度乘法
        //只能是两个正数相乘
        //速度更快，因为内嵌了加法计算
        //高精度除法
        //两个正数相除，商为quotient,余数为residue
        //需要高精度减法和乘法，无法加快。
        void div(string str1, string str2, string &quotient, string &residue)
        {
            quotient = residue = ""; //清空
            if (str2 == "0")         //判断除数是否为0
            {
                quotient = residue = "ERROR";
                return;
            }
            if (str1 == "0") //判断被除数是否为0
            {
                quotient = residue = "0";
                return;
            }
            int res = compare(str1, str2);
            if (res < 0)
            {
                quotient = "0";
                residue = str1;
                return;
            }
            else if (res == 0)
            {
                quotient = "1";
                residue = "0";
                return;
            }
            else
            {
                int len1 = str1.length();
                int len2 = str2.length();
                string tempstr;
                tempstr.append(str1, 0, len2 - 1);
                for (int i = len2 - 1; i < len1; i++)
                {
                    tempstr = tempstr + str1[i];
                    tempstr.erase(0, tempstr.find_first_not_of('0'));
                    if (tempstr.empty())
                        tempstr = "0";
                    for (char ch = '9'; ch >= '0'; ch--) //试商
                    {
                        string str, tmp;
                        str = str + ch;
                        tmp = mul(str2, str);
                        if (compare(tmp, tempstr) <= 0) //试商成功
                        {
                            quotient = quotient + ch;
                            tempstr = sub(tempstr, tmp);
                            break;
                        }
                    }
                }
                residue = tempstr;
            }
            quotient.erase(0, quotient.find_first_not_of('0'));
            if (quotient.empty())
                quotient = "0";
        }
    } sky;
    string rest;

 public:
    MyInteger()
    {
        bignum = "0";
    } //默认构造很熟构造函数, 默认值为0
    MyInteger(string &num)
    {
        int o = 0;
        int i;
        for (i = 0; i < num.size(); i++)
        {
            if (num[i] != 0)
                break;
        }
        for (i, o; i < num.size(); i++, o++)
        {
            bignum[o] = num[i];
        }
    } // 构造函数，从字符符串构造为大整数。
    MyInteger(int num)
    {
        char a[101];
        memset(a, 0, sizeof(a));
        sprintf(a, "%d", num);
        for (int i = 0; i < strlen(a); i++)
            bignum += a[i];
    }               // 构造函数，从整型构造为大整数。
    ~MyInteger(){}; // 析构函数
    string getnum()
    {
        return bignum;
    } // 返回表示大整数的字符字符串，注意去除前导零。//除法部分不完善。
    MyInteger operator+(const MyInteger &bint2)
    {
        MyInteger sum;
        sum.bignum = sky.add(bignum, bint2.bignum);
        return sum;

    } //大整数加法
    MyInteger operator-(const MyInteger &bint2)
    {
        MyInteger minus;
        minus.bignum = sky.sub(bignum, bint2.bignum);
        return minus;

    } //大整数减法
    MyInteger operator*(const MyInteger &bint2)
    {
        MyInteger multiplyer;
        multiplyer.bignum = sky.mul(bignum, bint2.bignum);
        return multiplyer;
    } //大整数乘法
    MyInteger operator/(const MyInteger &bint2)
    {
        MyInteger divisioner;
        sky.div(bignum, bint2.bignum, divisioner.bignum, divisioner.rest);
        return divisioner;
    }
};

int main()
{
    MyInteger dp[3001];
    dp[1]=1;
    dp[2]=2;
    dp[3]=4;
    for(int i=4;i<=3000;i++)
    {
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
    }
    int n;
    while(cin>>n)
    {
        cout<<dp[n].getnum()<<endl;
    }
    system("pause");
    return 0;
}

DP-2 最大子段和

题目信息

题目描述：

输入若干个整数，有正有负，要求用动态规划算法计算最大子段和，并输出这个和。注意子段为一段连续的数，同时规定全是负数的子段其和为0。

输入

第一行为一个整数，代表有组测试数据。 随后每组测试数据的第一行为，代表该组数据有个数。(接下来一行给出用空格隔开的这个整数。)

输出

每组测试数据输出一行，即最大子段和。

样例输入

1
8
-2 10 8 -4 7 5 -29 10

样例输出

26

数据范围

保证结果不超过

题目分析

最大子段和是最经典的模板题之一，对于字段的定义有必要强调一下：字段是指连续的一串数列串。

对于一个全为非负数的序列，最大子段和很好找，就是整个序列，因为不可能越加越少——加的数字越多，和一定越大。但是有个问题，如果有负数呢？

最大判断就会从此产生：如果对于一个已经求好从到间（的最大子序列和，如果有，则从到间最大子序列和为；否则为，即方程：

;

代码

#include<bits/stdc++.h>
using namespace std;
long long dp[1000001];
long long a[1000001];
const int INF=-0x7f7f;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        dp[0]=INF;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            dp[i]=INF;
        }
        for(int i=1;i<=n;i++)
        {
            dp[i]=max(dp[i-1]+a[i],a[i]);
        }
        sort(dp+1,dp+1+n);
        if(dp[n]>=0)cout<<dp[n]<<endl;
        else cout<<0<<endl;
    }
    system("pause");
    return 0;
}

DP-3 最大子阵和

题目信息

题目描述：

有一个包含正数和负数的二维数组。一个子矩阵是指在该二维数组里，任意相邻的下标是或更大的子数组。一个子矩阵的和是指该子矩阵中所有元素的和。本题中，把具有最大和的子矩阵称为最大子矩阵。

例如：

这个数组的最大子矩阵为：

其和为。

输入

输入包含多组测试数据。每组输入的第一行是一个正整数，表示二维方阵的大小。接下来行每行输入个整数，表示数组元素，范围为。

输出

输出最大子阵和。

样例输入

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

样例输出

15

数据范围

已给出

题目分析

核心的思想是把二维矩阵变为一维数组，然后求解一个最大子段和问题。

简单点说：我们认为暴力规定好每个子矩阵的行数，然后交给最大子段和来求解子矩阵的列数。

举个例子：

转化为：

然后对每一行最大子段和，找到所有行里面最大的。

代码

#include <bits/stdc++.h>
using namespace std;
int a[101][101];
int p[101];
int dp;
const int INF = -0x7f7f7f;
int ans;
int main()
{
    int n;
    while (cin >> n)
    {
        ans=dp=INF;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                cin >> a[i][j];
            }
        }
        for (int i = 1; i <= n; i++)
        {
            memset(p, 0, sizeof(p));
            for (int j = i; j <= n; j++)
            {
                dp=0;
                for (int k = 1; k <= n; k++)
                {
                    p[k] += a[j][k];
                    dp+=p[k];
                    if(dp<0)dp=p[k];
                    if(dp>ans)ans=dp;
                }
            }
        }
        cout << ans << endl;
    }
    system("pause");
    return 0;
}

DP-4 最长上升子序列

题目信息

题目描述：

给出一个由n个数组成的序列，求最长单调上升子序列的长度。即求最大的一个子序列长度，使得且。

输入

两行：

第1行：整数n

第2行：n个整数（范围内），空格隔开。

输出

一行：一个整数，即最长上升子序列长度。

样例输入

10
63  11  21  36  28  20  57  37  82  4

样例输出

5

题目分析

最长上升子序列同属于经典的模板之一。

代码