这里不再剖析如何理清和理解DP问题的思路，而是仅仅记录同一类DP问题，希望从更细小的角度对这类特定问题形成更深刻的印象和理解，并泛化到对一般DP的理解上

先说结论：

本文记录的一类DP问题，【动首动脚】导致的状态转移，用dp table来刻画就是从下到上从左到右的右上三角填充

例1 leetcode 5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串，子串是连续的。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

本题个人认为是右上三角DP的base题目
思路：
一个子串A回文 = 头尾相等 + 去头尾后的子串B回文
上面这个式子建立了子问题间的状态转移关系，容易想到dp，分述如下：

• 对于字符串s，考虑一个二维DP矩阵，dp[i][j]表示s[i:j+1]是否回文，是True，否False
• 初始化dp：对于每一个i，i<len(s)，dp[i][i] = True，表示任意一个字符都是回文的
• 填充dp：根据状态转移方程，dp[i][j] = dp[i+1][j-1] and s[i] == s[j]，易得填充方向是从下往上，从左往右
• 在填充过程中，不断更新res

整个dp table如图所示

最长回文子串-右上三角dp

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return s
        res = s[0]
        l = len(s)
        dp = [[True for i in range(l)] for j in range(l)]
        
        # 填充dp
        for i in range(l-1, -1, -1):
            j = i + 1
            while j < l:
                # 状态转移方程
                dp[i][j] =  dp[i+1][j-1] and s[i] == s[j]
                if dp[i][j]:
                    if j - i + 1 > len(res):
                        res = s[i:j+1]
                j += 1
        return res

本质上讲，一个回文串是在另一个回文串的基础上【增减相同的首尾】得来，这种【动首动脚】的操作反映在dp table上，就是 dp[i][j] 与 dp[i+1][j-1] 建立了转移关系；而根据这个转移关系可知，必然先有dp[i+1][j-1]再有dp[i][j]，因此填充方向从下到上从左到右

综上，我们看到，【动首动脚】导致的状态转移，用dp table来刻画就是从下到上从左到右的右上三角填充。这句话是这篇文章的核心

例2 leetcode 486. 预测赢家

给定一个表示分数的非负整数数组nums。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化

题干关键词，从数组任意一端拿取，符合“动首动脚”的情况，考虑右上三角dp

• dp[i][j]表示玩家在nums[i:j+1]下先拿时能够比另一玩家多拿的最大分数
• 状态转移：dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i:j-1])。即，玩家可以拿nums[i]，也可以拿nums[j]，从中取收益最大的
• 从状态转移方程可以看出，dp[i][j] 由其左侧和下侧转移而来，dp table的填充方向仍然是从下往上，从左往右
• 最后判断dp[0][len(nums)-1]是否大于0

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        # dp法
        # dp[i][j] 表示 nums[i:j+1]规模下的先手比对手多的最大分数

        l = len(nums)
        dp = [[0 for i in range(l)] for j in range(l)] 
        # 初始化dp
        for i in range(l):
            dp[i][i] = nums[i]
        
        # 从下往上，从左往右填充dp
        for i in range(l-2, -1, -1):
            j = i + 1
            while j < l:
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
                j += 1
        return dp[0][l-1] >= 0

例3 leetcode 1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让 s 成为回文串的 最少操作次数

• 本题最直观的思路就是先求出s的最长回文子序列，与s的长度差为所求，代码如下不再赘述

class Solution:
    def minInsertions(self, s: str) -> int:
        # 求最长回文子序列
        s1 = s[::-1]
        l = len(s)
        dp = [[0 for i in range(l+1)] for j in range(l+1)]
        # dp初始化
        for i in range(1, l+1):
            for j in range(1, l+1):
                if s[i-1] == s1[j-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return l - dp[-1][-1]

• 另外还有一种【动首动脚】的与本文相关的解法，关键在于定义dp要记录什么状态。dp是考虑局部问题的转移关系作为切入点的，把大问题看成由子问题不断扩大规模得到，那么令dp[i][j]表示s[i:j+1]的最少操作次数，这样可以和相邻的dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]子问题建立联系，因为dp[i][j]可以由dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]动首动脚得来。如此，状态转移方程就不难得出。代码如下

class Solution:
    def minInsertions(self, s: str) -> int:
        # dp[i][j]表示s[i:j+1]的最少操作次数
        # if s[i] == s[j]: dp[i][j] = dp[i+1][j-1]
        # if s[i] != s[j]: dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

        l = len(s)
        dp = [[0 for i in range(l)] for j in range(l)]
        for i in range(l-1, -1, -1):
            j = i + 1
            while j < l:
                if s[i] == s[j]: dp[i][j] = dp[i+1][j-1]
                if s[i] != s[j]: dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
                j += 1
        return dp[0][-1]