voidbinarysearchtree(inta[],intb[],intn,int**m,int**s,int**w){inti,j,k,t,l;for(i=1;i<=n+1;i++){w[i][i-1]=a[i-1];m[i][i-1]=0;}for(l=0;l<=n-1;l++)//----l是下标j-i的差for(i=1;i<=n-l;i++){j=i+l;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];s[i][j]=i;for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j]+w[i][j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}

运用的是动态规划的思想，由于是求最长回文字符串。dp数组定义为：在子串s[i…j]中，最长回文子序列的长度为dp[i][j];子问题：所以其子问题可以看作是求短一点长度，例如求dp[i][j],可以由求其子问题dp[i+1][j-1]的结果算出。所以其子问题即是长度减去左右两端的字符串的长度。递推公式:dp[i][j]=dp[i+1][j-1]+2s[i]==s[j]dp[i][j]=max(dp[i+1][j],dp[i][j+1])s[i]!=s[j]getLength(str):输入：一个字符串输出：字符串内最长回文字符串的长度fori<--length-1to0do:dp[i][i]=1;forj<--i+1tolength-1do:If(str[i]==str[j])then:dp[i][j]=dp[i+1][j-1]+2;elsedp[i][j]=max(dp[i+1][j],dp[i][j+1])endendreturndp[0][len-1];

相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标+1的两个结点。示例[[2],[3,4],[6,5,7],[4,1,8,3]]自顶向下的最小路径和为11（即，2+3+5+1=11）。说明：如果你可以只使用O(n)的额外空间（n为三角形的总行数）来解决这个问题，那么你的算法会很加分。///MemorySearch///TimeComplexity:O(n^2)///SpaceComplexity:O(1)classSolution{public:intminimumTotal(vector<vector<int>>&triangle){intn=triangle.size();vector<vector<int>>dp(n,vector<int>(n,-1));for(inti=0;i<n;i++)go(triangle,n-1,i,dp);return*min_element(dp[n-1].begin(),dp[n-1].end());}private:intgo(constvector<vector<int>>&triangle,inti,intj,vector<vector<int>>&dp){if(dp[i][j]!=-1)returndp[i][j];if(i==0)returndp[i][j]=triangle[i][j];if(j==0)returndp[i][j]=triangle[i][j]+go(triangle,i-1,0,dp);if(j==i)returndp[i][j]=triangle[i][j]+go(triangle,i-1,i-1,dp);returndp[i][j]=triangle[i][j]+min(go(triangle,i-1,j-1,dp),go(triangle,i-1,j,dp));}};///DynamicProgramming///TimeComplexity:O(n^2)///SpaceComplexity:O(1)classSolution{public:intminimumTotal(vector<vector<int>>&triangle){intn=triangle.size();for(inti=1;i<n;i++){triangle[i][0]+=triangle[i-1][0];triangle[i][i]+=triangle[i-1][i-1];for(intj=1;j<i;j++)triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j]);}return*min_element(triangle[n-1].begin(),triangle[n-1].end());}};

选择二叉树中不相邻的节点，使得节点之和为最大。///MemorySearch///TimeComplexity:O(n),wherenisthenodes'numberinthetree///SpaceComplexity:O(n)classSolution{public:introb(TreeNode*root){returnrob(root,true);}private:introb(TreeNode*root,boolinclude){if(root==NULL)return0;intres=rob(root->left,true)+rob(root->right,true);if(include)res=max(root->val+rob(root->left,false)+rob(root->right,false),res);returnres;}};///Redefinetherecursivefunctionandreturnatwo-elementarray///representtheincludeandexcludemaximumresultforrobbingthenode//////TimeComplexity:O(n),wherenisthenodes'numberinthetree///SpaceComplexity:O(1)classSolution{public:introb(TreeNode*root){vector<int>result=tryRob(root);returnmax(result[0],result[1]);}private:vector<int>tryRob(TreeNode*root){if(root==NULL)returnvector<int>(2,0);vector<int>resultL=tryRob(root->left);vector<int>resultR=tryRob(root->right);vector<int>res(2,0);res[0]=resultL[1]+resultR[1];res[1]=max(res[0],root->val+resultL[0]+resultR[0]);returnres;}};