6.12随笔(dp问题)
又被一个dp锤爆了
先来说一下今天wa32次的收获
1.dp问题很重要的一个性质就是无后效性
,即更新到位置i
时,1~i-1
应该都是最优解
2.每个问题都可以转换为子问题来解决,也就是可以用前面已经更新的子最优解来更新当前位置的最优解
3.更新第i个位置时,要用前面所有可能可以更新位置i的位置更新
上题目:传送门
这题位置i的状态可以用两种方式转移:
1.if (a[i - 1] == a[i] - 1)dp[i] = min(dp[i], dp[i - 1] + 1);
2.从位置j(1<j<i )退到位置k(1<k<j),如果可以跳到位置i,那么就可以尝试更新。
代码:
1 | ll a[210], dp[210]; |