复旦大学机试真题

复旦大学机试真题

【2016-1】DP-求最大连续公共字串长度

题目描述：给定两个字符串，求最大公共字串的长度，长度小于1000
分为两种问题：要求计算连续最长字串的长度
如下按照寻找连续的字串理解
输入：
1111hello2222
1133hello444
输出：
5

int dp[1010][1010];
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size()+1;int n = text2.size()+1;for(int i=0;i<=m;++i){dp[i][0] = 0; }for(int j=0;j<=n;++j){dp[0][j] = 0;}for(int i=1;i<=m;i++){for(int j=1;j<=n;++j){if(text1[i-1]==text2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = max(dp[i][j-1],dp[i-1][j]);}}}return dp[m-1][n-1];}
};

【2018-3】DP

问题描述：有2 * n 的地板，用1 * 2和2 * 1的骨牌进行铺地板。问共有多少种情况。结果对 999983 取余，1<=n<=10000
输入：
6
输出：
13

#include<iostream>
using namespace std;
typedef long long ll;
ll dp[2001];
ll gupai(int n){dp[1] = 1;dp[2] = 2;if(n<3) return n;for(int i=3;i<=n;++i){dp[i] = dp[i-1]%999983 + dp[i-2]%999983;}return dp[n];
}
int main(){int n;while(cin>>n) {cout<<gupai(n)<<endl;}
}

【2019-2】DP-最大连续子序列和

题目描述：给定一个数组及其大小，数组元素在[-106，106]，元素个数最多 10^6 个。输出最大的连续子序列和，题目保证最后结果为正数。

const int MAXN = 1e6+10;
int dp[MAXN];
class Solution {
public:int maxSubArray(vector<int>& nums) {dp[0] = nums[0];if(nums.size()==1) return nums[0];int re = dp[0];for(int i=1;i<nums.size();++i){dp[i] = max(nums[i],dp[i-1]+nums[i]);re = max(re,dp[i]);}return re;}
};