Leetcode.5
做题时间：2016/10/11
问题描述：
求一个字符串的最长子回文串。
解题思路：
- 用动态规划的思想来解题。动态规划两个性质：最优子结构和重叠子问题。所以首先要找到问题的子问题。
- 要求一个字符串的回文子串 ，回文子串的子串也是回文子串，所以可以考虑先求1个长度的回文子串，两个长度的回文子串.....用d[i][j]＝1来表示子串i~j是回文子串，这样只要判断d[i+1][j-1]==1并且s[i]==s[j]，就可以确定d[i]d[j]是回文子串。
- 用自底向上的方法，先求出子问题，再求解问题。
解题遇到的问题
- 初始条件是令d[i][i]=1,并判断d[i][i+1]，接着应该是再求解长度为3的子问题、长度为4的子问题、长度为5的子问题.....，所以循环时应该最外层是子串长度的循环。
- c++中的返回一个字符串的子串的函数s.substr(a,b)，a代表开始的那个下标，b代表要返回的子串的长度。
Leetcode.53
做题时间：2016/10/13
问题描述：
求一个数组的最大子数组和。
解题思路：
- 用动态规划的思想来解题。
- t[i]代表以第i个元素结尾的最大连续子数组的和，在遍历过程中，有两种情况，在加上n[i]时，如果t[i]<0，那么就应该以n[i]为起点重新寻找起始数。
Leetcode.62
做题时间：2016/10/15
问题描述：
设有一个m*n的网格，要求从(0,0)到(m-1,n-1)的路径条数（每一次只可以向右移动一格或者向下移动一格）。
解题思路：
- 用动态规划的思想来解题。
- 要求到达d[m][n]位置的路径条数，就是求d[m-1][n]+d[m][n-1]之和。另外，从(0,0)到达最上一行（m=0）和最左边一列（n=0）任意一个网格的路径条数都是一，可是进行初始化。
解题遇到的问题
- 在用
vector<vector<int>>d[m]时出错，应当是vector<vector<int>>d(m)。