概述

在做动态规划题时，常常陷入困惑，面对的几个挑战分别是

1. d数组如何设置？设置成一维还是二维？dp[n]还是dp[n+1]?
2. 状态转移方程怎么考虑？

分类

自我比较带约束

最长回文子串

设置dp[n][n],dp[i][j]表示s[i:j]的回文长度

最长的括号子串

设置dp[n],dp[i]表示s[:i]的子串长度

买卖股票的最好时机

设置dp[n],dp[i]表示s[:i]的利润

矩阵的最小路径和

设置dp[n][m],dp[i][j]表示到达矩阵[i][j]的路径和

求矩阵路径数

设置dp[n][m],dp[i][j]表示到达矩阵[i][j]的路径数

两两比较带约束

最小编辑代价

设置dp[n][m],dp[i][j]表示字符串1[:i]编辑为字符串2[:j]的代价

最长公共子序列

设置dp[m][n],dp[i][j]表示字符串1[:i]和字符串2[:j]比较的最大长度