建网站公司用什么网站程序,常熟市住房建设局网站,怎么建设游戏网站,wordpress怎么社交分享我昨天面了天美L1的游戏客户端开发#xff0c;面了我100分钟#xff0c;问完实习、项目、计算机图形学和C后给了我两道算法题做#xff0c;一道是最长公共子序列#xff0c;一道是LRU缓存#xff0c;我知道是经典的题目#xff0c;但是我都没敲过#xff0c;最长公共子序…我昨天面了天美L1的游戏客户端开发面了我100分钟问完实习、项目、计算机图形学和C后给了我两道算法题做一道是最长公共子序列一道是LRU缓存我知道是经典的题目但是我都没敲过最长公共子序列面试前一晚运气好随口问了一下GPT的解决思路记得是二维的动态规划
原题1143. 最长公共子序列 - 力扣LeetCode
为什么用动态规划呢因为最长公共子序列具有最优子结构性质子问题的最优解之间互不影响而原问题的解可以由子问题的解推出来记dp[i][j]是两个字符串的前i个和前j个子串的最长公共子序列LCS的长度如果此刻遍历到的两个字符是相同的那么dp[i][j]就应该等于dp[i-1][j-1]1否则应该是dp[i-1][j]和dp[i][j-1]的较大者
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorintdp(text1.size()1,vectorint(text2.size()1));for(int i1;itext1.size();i){for(int j1;jtext2.size();j){if(text1[i-1]text2[j-1])dp[i][j]dp[i-1][j-1]1;elsedp[i][j]max(dp[i-1][j],dp[i][j-1]);}}return dp[text1.size()][text2.size()];}
};
