1. 比特位计数

（1）res[i]含义：数字 i 二进制中1的个数

（2）数组关系：

1. 奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
2. 偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。

（3）边界条件：res[0]=0;

class Solution {
public:vector<int> countBits(int num) {vector<int> res(num+1);res[0]=0;for(int i=1; i<=num;i++){if(i%2==0){res[i]=res[i/2];}else{res[i]=res[i/2]+1;}/*位运算可能更易理解本题//  x / 2 is x >> 1 and x % 2 is x & 1 res[i]=res[i>>1] + (i&1);*/}return res;}
};

2. 爬楼梯

（1）dp[i]含义：爬到第i层台阶的方法总数

（2）数组关系：dp[i]=dp[i-1]+dp[i-2]

（3）边界条件：dp[0]=1,dp[1]=1;

class Solution {
public:int climbStairs(int n) {vector<int> dp(n+1);dp[0]=1;  //可由dp[2]推出dp[1]=1;for(int i=2; i<=n; i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};

3. 解码方法 (把数字翻译成字符串）

（1）dp[i] 含义：以 s[i] 结尾的前缀子串有多少种解码方法

（2）数组关系：

如果s[i]='0' : 在s[i-1]='1' 或者 s[i-1]='2'情况下，即此时s[i]不能单独翻译，则dp[i]=dp[i-2]，否则return 0；

如果s[i-1]=’1‘ 或者 s[i-1]='2' && s[i]在1~6范围内，此时s[i]可以单独翻译，也可以和s[i-1]合并翻译，则dp[i]=dp[i-1]+dp[i-2];

否则s[i]只能单独翻译，则dp[i]=dp[i-1]；

（3）边界条件：由于涉及dp[i-2]，所以可增设一个dp值，以dp[0]=1,dp[1]=1为边界，最后返回dp[len]

class Solution {
public:int numDecodings(string s) {if(s[0]=='0')  return 0;int len=s.size();vector<int> dp(len+1);dp[0]=1;dp[1]=1;for(int i=1; i<len; i++){if(s[i]=='0'){if(s[i-1]=='1' || s[i-1]=='2'){dp[i+1]=dp[i-1];}else{return 0;}}else{if(s[i-1]=='1' || (s[i-1]=='2' && s[i]<='6')){  dp[i+1]=dp[i]+dp[i-1];}else{dp[i+1]=dp[i];}}}return dp[len];}
};

 4.最长上升子序列

（1）dp[i] 含义：表示以 nums[i] 结尾的上升子序列长度

（2）状态转移方程：在下标 i 之前严格小于 nums[i]  的所有状态值中的最大者 + 1。

（3）边界条件：dp[i] 所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n=nums.size();vector<int> dp(n,1);int res=0;for(int i=0; i<n; i++){for(int j=0; j<i; j++){if(nums[i]>nums[j]){dp[i]=max(dp[i],dp[j]+1);}}res=max(res,dp[i]);}return res;}
};

5.最长回文子串

思路：对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串 。

（1）dp[i][j]定义：表示字符串 s 的第 i 到 j 个字母组成的串是否是回文子串

（2）状态转移：若s[i]==s[j]  , 那么dp[i][j]=dp[i+1][j-1];

（3）边界条件：上述前提子串长度>2;   故考虑子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，即 j - 1 - (i + 1) + 1 < 2 ，整理得 j - i < 3。因此，在 s[i] == s[j] 成立和 j - i < 3 的前提下，直接可以下结论，dp[i][j] = true，否则才执行状态转移。

动态规划是个填表的过程：

class Solution {
public:string longestPalindrome(string s) {if(s.size() < 2)    return s;int start = 0, maxlen = 1, n = s.size();vector<vector<int>> dp (n,vector<int>(n));for(int i = 0; i < n; ++i)dp[i][i] = true;        //对角线均为true,因为一个元素肯定是回文子串for(int j = 1; j < n; ++j){for(int i = 0; i < j; ++i){if(s[i] != s[j])    dp[i][j] = false;else{if((j-1) - (i+1) + 1 < 2)   dp[i][j] = true;    //如果内部区间长度小于等于1else{if(dp[i+1][j-1])    dp[i][j] = true;        //看内部区间是否是回文}}if(dp[i][j] && j - i + 1 > maxlen)  {start = i;maxlen = j - i + 1;  }  }}return s.substr(start,maxlen);}
};