Day60 动态规划总结

647. 回文子串

回文的做法注定我们得从里面入手，逐渐扩散到边界

初始化：准备一个ans，找到一个回文子串加一个

        dp = [[0] * n for _ in range(n)]ans = 0

遍历公式： 当s[i]==s[j]的时候，只要里面还是回文串，就能说明s[i:j + 1]是回文串

                if s[i] == s[j]:if j - i > 2:if dp[i + 1][j - 1] == 1:ans += 1dp[i][j] = 1else:ans += 1dp[i][j] = 1

516.最长回文子序列

与上题不同，此题找的是最长回文子序列，回首前面的数组子序列题，我们要注意好继承的情况，以及dp数组的含义应该是：当前包含的最长回文子序列的长度。

初始化：每个回文串的最低长度都为1

        dp = [[1] * n for _ in range(n)]

遍历公式： 字符相同，就在原最长长度上加2，不然就继承最长数目

                if s[i] == s[j]:if j - i > 1:dp[i][j] = dp[i + 1][j - 1] + 2else:dp[i][j] = j - i + 1else:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

动态规划总结

写法总结：

1.创建dp数组，做好数组下标定义是成功的基础

2.初始化注意题目要求

3.遍历公式注意数组下标定义

4.遍历顺序注意题目求解

5.dp举例验证结果正确性

类型区分：

1.爬楼梯与路径问题

从过程得到结果

2.背包问题

组合数与排列数，01亦或完全，更多时候需要对题目进行解读，能否转换成背包问题是关键

3.打家劫舍

线性，环形，树状打劫，归根究底注意偷与不偷的状态区分

4.股票买卖

买与卖的遍历公式，已经更多状态就需要改变dp数组进行状态压缩来达到目的

5.编辑距离

子数组与子序列的遍历区分，以及不同题目要求的遍历公式的微妙区别

6.回文字符串

回文特点运用于字符串，从里到外是关键顺序

Need have brave to beat issues with facing endless failures.