March 7th: Palindrome Partitioning

• tags: dfs, dp, 记忆化搜索
• problem: https://leetcode-cn.com/problems/palindrome-partitioning/

dfs

其实dfs就是第一层循环内递归
在这题中，用dfs判断以i起点的子串是否能划分成【所有划分都是回文串】，就是
1.【回文串划分】以i为起点的子串一次，找到边界j0, j1, j2, ...
2. 再次对每个j调用dfs判断余下的子串[j+1, ...]。

void isValidPart(str, i)
{
  // termination
  if(i == n)
  {  
    ans.push_back(ans_part);
    return;
  }
  // recursion
  for(int j = i; j < n; ++j)
  {
    if(isPalindrome(str, i, j))
    {
      ans_part.push_back(str.substr(i, j - i + 1));
      isValidPart(str, j + 1);
      ans_part.pop_back();
    }
  }

dp

dp关键思想就是递推式（由已知得未知）
在这题中，dp用来判断一个子串是否是回文串

dp[i][j] = (str[i] == str[j] && dp[i+1][j-1])

记忆化搜索

记忆化搜索是懒惰搜素，并记录搜索过程中产生的所有有用结果，迎合了dp的需求

在这题中，不适用遍历所有(i, j)来计算所有dp，仅当(i, j)需要被获取时才递归地计算并记录。

• 令dp[i][j]有三态：enum{TRUE, FALSE, NO_RECORED}
• 每次调用都记录结果：return dp[i][j] =

int isPalindrome(str, i, j)
{
  if(dp[i][j])
    return dp[i][j];
  if(i >= j)
    return dp[i][j] = true;
  return dp[i][j] = (str[i] == str[j]) ? isPalindrome(str, i+1, j-1) : false;
}

每日一题——不定时日更

原文：https://www.cnblogs.com/laiyk/p/14493702.html