- 给定一个序列
- 动态规划方程
f[i]中的下标i表示前i个元素a[0] a[1] ... a[i-1]的某种性质- 坐标型的
f[i]表示
为结尾的某种性质
- 坐标型的
- 初始化中，
f[0]表示空序列的性质- 坐标型动态规划的初始条件
f[0]就是指以
为结尾的子序列的性质
- 坐标型动态规划的初始条件
2.1
2.2
2.3
2.4 题目解析
843 · 数字翻转
解析
题意：
- 给定一个长度为
N的01串要求翻转其中最少的01，使得结果中没有
"01"这样的子串例子：
- 输入：
[1 0 1 0 1 0]- 输出：2 （变成
[1 1 1 1 1 0]）确定状态：
- 最后一步：最优策略中，最后一位数是否翻转
- 但是需要知道前一位数已经变成
0还是1- 并且前
N-1位数最少翻转多少次，满足要求（无01子串）- 不知道的信息加入状态里
- 状态
- 用
f[i][0]表示A[i-1]变成0的情况下，前i位最少翻转多少个能满足要求- 用
f[i][1]表示A[i-1]变成1的情况下，前i位最少翻转多少个能满足要求初始条件和边界情况：
题目
:::info
:::
👋
样例
Input:
Output:
:::success
:::
Explain:
:::warning
:::
Input:
Output:
:::success
:::
Explain:
:::warning
代码
515 · 房屋染色
解析
题意：
确定状态：
子问题：
转移方程：
初始条件和边界情况：
计算顺序：
题目
:::info
:::
👋
样例
Input:
Output:
:::success
:::
Explain:
:::warning
:::
Input:
Output:
:::success
:::
Explain:
:::warning
代码
小结
电话面试
若有收获，就点个赞吧
0 人点赞
