s647. 回文子串

  1. class Solution {
  2. public:
  3.     int countSubstrings(string s) {
  4.         // dp[i][j] s[i,j]是否是回文子串
  5.         int n = s.size(), res = 0;
  6.         vector<vector<bool>> dp(n, vector<bool>(n, false));
  8.         for (int i=0; i<n; i++)
  9.         {
  10.             for (int j=0; j<=i; j++)
  11.             {
  12.                 // 只有一个字符 ｜｜ 去除两边的子串是回文
  13.                 if (s[i] == s[j] && (i-j<2 || dp[j+1][i-1]))
  14.                 {
  15.                     dp[j][i] = true;
  16.                     res++;
  17.                 }
  18.             }
  19.         }
  20.         return res;
  21.     }
  22. };

516. 最长回文子序列

这里的遍历顺序，完全是根据状态转移方程来设定的，保证用到时，已经计算出来了即可。

  1. class Solution {
  2. public:
  3.     int longestPalindromeSubseq(string s) {
  4.         int n = s.size();
  5.         vector<vector<int>> dp(n, vector<int>(n, 0));
  7.         for (int i=0; i<n; i++)
  8.         {
  9.             dp[i][i] = 1;
  10.             for (int j=i-1; j>=0; j--)
  11.             {
  12.                 if (s[j] == s[i])
  13.                     dp[j][i] = max(dp[j+1][i-1] + 2, dp[j][i]);
  14.                 else 
  15.                     dp[j][i] = max(dp[j+1][i], dp[j][i-1]);
  16.             }
  18.         }
  20.         return dp[0][n-1];
  21.     }
  22. };

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.         /*
  5.         1. 先求数组的总和sum
  6.             a. sum奇数， 返回false
  7.             b. sum偶数
  8.                 i. 将问题转化为01背包问题，然后进行求解
  9.                     target = sum/2
  10.         */
  13.         int sum = accumulate(nums.begin(), nums.end(), 0);
  15.         if (sum & 1) return false;
  17.         int n = nums.size(), m = sum / 2;
  18.         vector<vector<int>> f(n+1, vector<int>(m+1, 0));
  20.         for (int i=1; i<=n; i++)
  21.         {
  22.             for (int j=1; j<=m; j++)
  23.             {
  24.                 int wv = nums[i-1];
  25.                 if (j >= wv)
  26.                     f[i][j] = max(f[i-1][j], f[i-1][j-wv] + wv);
  27.                 else 
  28.                     f[i][j] = f[i-1][j];
  29.             }
  30.         }
  32.         if (f[n][m] == m) return true;
  34.         return false;
  36.     }
  37. };

空间优化

  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.         int sum = accumulate(nums.begin(), nums.end(), 0);
  6.         if (sum & 1) return false;
  8.         int n = nums.size(), m = sum / 2;
  9.         vector<int> f(m+1, 0);
  11.         for (int i=1; i<=n; i++)
  12.         {
  13.             int wv = nums[i-1];
  14.             for (int j=m; j>=wv; j--)
  15.                 f[j] = max (f[j], f[j-wv] + wv);
  16.         }
  18.         if (f[m] == m) return true;
  20.         return false;
  21.     }
  22. };