思路：考虑中间状态   ·设D[i][j]为棋盘位置(i,j)时，可以获得的最大价值;val[i][j]为（i

正确答案是C动态规划，利用问题的最优子结构性质，以自底向上的方式递归的从子问题的最优解逐步构造出整个问题的最优解。对于重叠子问题，一个典型的问题是求斐波那契数列的第N项.如果用递归的方法做会存在大量的重叠子问题，而利用动态规划的方法就是解决了重叠子问题。建立表格不断填表，相当于备忘录，也就是解决重叠子问题的技巧，典型的问题是斐波那契数列、背包问题等，许多动态规划问题都是定义数组，进行递推过程填充数组（模拟备忘录）。马尔科夫性，是随机过程中某事件的发生只取决于它的上一事件、是“无记忆”过程。而动态规划具有“记忆性”。

分治和动态规划：共同点：两者都是把大问题转换成小问题/子问题来解决，并且当最优子问题组合成最优大问题，关键点在于找到子问题的划分。不同点：分治采用递归写法，当子问题之间没有重复的时候，是很好的方法，但当子问题之间存在重复的时候，分治方***重复计算子问题很多次，碰到一次算一次，因为分治是自上而下的，往下走的过程中，每次碰到相同的子问题都要重复计算，时间复杂度很高。动态规划，专门针对这种存在重复子问题的分解算法，并且每一个大问题都可以由它的子问题的最优解来表示；因此，动态规划采用自下而上的方法，先计算最小的子问题的最优解，再一层层组合成大问题的最优解，计算过程中不存在子问题的重复计算。

运用的是动态规划的思想，由于是求最长回文字符串。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());}};