OJ——动态规划:最长公共子序列/最长上升子序列/最长回文子序列/最大子数组_最长公共上升子序列 loj

动态规划题目练习列表：（都是经典，具体题目瞬间可搜）

1.最长公共子序列

2.最长上升子序列

3.最长回文子序列

4.最大子数组

5.矩阵链连乘

6.数塔问题

7.硬币问题

8.背包问题

经典五题，不如先做：https://blog.csdn.net/zmazon/article/details/8247015

这篇文章不错：https://blog.csdn.net/eagle_or_snail/article/details/50987044

知乎，关乎思想：https://www.zhihu.com/question/23995189

 

1.最长公共子序列（POJ1458）

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
 
int main(){  
    string str1,str2;
    while(cin>>str1>>str2){
        vector<vector<int> >dp(str1.length()+1,vector<int>(str2.length()+1,0));  //创建动态规划数组并初始化
 
        for (int i=1; i < str2.length() + 1; i++) {  //填表
			for (int j=1; j < str1.length() + 1; j++) {
				if (str2[i-1] == str1[j-1]) {  //I mad a mistake here.
					dp[i][j] = dp[i - 1][j - 1]+1;
				}
				else {
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
 
        /*输出测试
        for(int i=0;i<=str1.length();i++){
            for(int j=0;j<=str2.length();j++){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }*/
 
        cout<<dp[str1.length()][str2.length()]<<endl;  //输出结果
    }
 
    return 0;
}

纠错：

• 动态规划的数组多一行和多一列的时候要注意和输入数据匹配一下。

心得：动态规划的一类题，只要会填表格就可以翻译出代码，真的！！！那么主要问题就是“表格”。

转移方程：

        如果dp数组行和列对应的内容相等，则为斜左上方的内容+1;

        如果不相等，则为上方或者左方较大的一个（如果相等取上方，代码）;

输入样例：

abcfbc         abfcab

样例表格：（dp过程）

 

表格画法：

                行和列分别是两个字符串的长度+1;多出来的一行和一列是用来初始化为0的;

                一行一行从上往下，从左往右填。

---

2.最长上升子序列（百练2757)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main_lis(){  //需要修改主函数
    int len;
    while(cin>>len){
 
 
 
        //数据的存储与输入
        vector<int>v(len);
        for(int i=0;i<len;i++){
            cin>>v[i];
        }
 
        //dp
        vector<int>dp(len,1);
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(v[i]>v[j]){  // I made a mistake here.
                    dp[i]=max(dp[j]+1,dp[i]);  //!! I made a mistake here
                }
            }
        }
 
        /*测试输出
        for(int i=0;i<len;i++){
            cout<<dp[i]<<" ";
        }
        cout<<endl;*/
 
        //结果 !! I forgot this part ever.
        int result=0;
        for(int i=0;i<len;i++){
            if(result<dp[i])result=dp[i];
        }
        cout<<result;
 
    }
 
    return 0;
}

 （做这道题的时候，自己有个很愚蠢的点，在处理个别样例的时候，判断过它后就直接输出结果了，甚至没有让该输入的样例输入完，这肯定会影响后续的结果）

纠错：

• 首先，dp更新的条件就错了，是输入数据自己和自己比。
• 其次，更新dp的式子是选最大的。因为j的那一层循环里面是有大有小的，要保证是最大的那一个。
• 最后，忘了结果。前面的算法是把每一个当作最后一个的时候的最长上升子序列。那么，所有的当然要在所有的里面找。

想法：这其实不是一个“想要整体，就从局部的过程”。因为最后的解决还要靠寻找最大值。

           每一个数，都能影响前面的整条，所以——先针对每一个数，在前面的里面找到最长上升子序列。

           最后，找出最大的。

样例：

1 7 3 5 9 4 8

dp过程：

前1个数：1

前2个数：27

前3个数：13

前4个数：135

前5个数：1359

前6个数：134

前7个数：1348

---

3.最长回文子序列（Leetcode:5）

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 
class Solution {
public:
    string longestPalindrome(string s) {
        int start=0, plus=0; 
        
        if(s.length()==0){  // cause run time error, if forget it
            return "";
        }
 
		//dp & init
		vector<vector<int> >dp(s.length(), vector<int>(s.length(), 0));
		for (int i = 0; i < s.length();i++) {
			dp[i][i] = 1;
		}
 
		for (int i = 0; i < s.length() - 1; i++) {
			if (s[i] == s[i + 1]) {
				dp[i][i + 1] = 1;  
				start = i;  // cause WA, if forget it
				plus = 1;
			}
		}
 
		//dp
		 
		for (int i = 2; i < s.length(); i++) {
			for (int j = 0; j+i < s.length(); j++) { // I made a mistake here  //  remember "j+i"
				if (s[j] == s[j + i]) {
					dp[j][j + i] =dp[j + 1][j + i - 1];
					if (dp[j + 1][j + i - 1] == 1&&plus<=i) {
							start = j;
							plus = i;
						
					}
					else {
						dp[j][j + i] = 0;
					}
				}
			}
		}
		return s.substr(start,plus+1);
		//cout << dp[0][input.length() - 1] << endl;
    }
};

纠错：

• 数组越界：dp的上三角填法，第二个循环的约束是“j+i<input.leng()”而不是“j<input.length()”
• 数组越界：题目的输入是字符串，忘记考虑特殊样例“” ，访问不到自然数组越界。
• WA:在输出处理的过程比较复杂的时候，只考虑了通常样例，没有考虑特殊样例。

心得：dp的输入如果是一个串，问串里面可能存在的情况，就填dp数组的上三角。

转移方程：

4.最大子数组（LeetCode:53）

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
    vector<int>dp(nums.size());
	int max_num=0;
 
	//init
	dp[0] = nums[0];
	max_num = nums[0];
 
	//dp
	for (int i = 1; i < nums.size(); i++) {
		dp[i] = max(dp[i - 1] + nums[i], nums[i]);  //name error
		if (max_num < dp[i]) {
			max_num = dp[i];
		}
	}
	//cout << max_num << endl;
	return max_num;
    }
};

心得：dp问题的数组也许无法记录最终的结果，常常要在过程中记录最值以表示结果。

转移方程：

---

5.动态规划0-1背包专题：（建设中。。。）