[已解决]求几道洛谷的dp题

sfqxx

rt,要求难度在普及/提高-一下

至少2道，并给出链接，注意是洛谷

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-8-18 13:16:56

https://www.luogu.com.cn/training/211#problems

要善于使用官方题单

跳转到最佳答案楼层

isdkz

当然，我可以给你提供几道洛谷的动态规划（dp）题目。以下是两道难度适中的题目，附上了洛谷的链接和解题思路：

1. [P1002 过河卒](https://www.luogu.com.cn/problem/P1002)
   这道题目是一个经典的棋盘路径问题。给定一个棋盘和一个马的初始位置和目标位置，求出马从初始位置移动到目标位置的所有路径数。可以使用动态规划来解决，定义一个二维数组dp，其中dp[ i][j]表示马从初始位置(0, 0)移动到位置(i, j)的路径数。根据马的移动规则，可以得到状态转移方程：dp[ i][j] = dp[i-1][j-2] + dp[i-2][j-1]。最终，dp[n][m]就是所求的答案。

2. [P1049 装箱问题](https://www.luogu.com.cn/problem/P1049)
   这道题目是一个经典的背包问题。给定一些物品的体积和一个背包的容量，要求选择一些物品放入背包中，使得物品的体积之和不超过背包的容量，并且尽量使得物品的体积之和最大。可以使用动态规划来解决，定义一个一维数组dp，其中dp[ i]表示背包容量为i时的最大体积。根据每个物品的体积，可以得到状态转移方程：dp[ i] = max(dp[ i], dp[i-v[j]] + v[j])，其中v[j]表示第j个物品的体积。最终，dp[容量]就是所求的答案。

希望这些题目能够帮助你练习动态规划的思维和技巧。如果还有其他问题，请随时提问。

Ewan-Ahiouy

你要学dp！好卷啊

https://www.luogu.com.cn/problem/P1002 过河卒

https://www.luogu.com.cn/problem/P1115 最大字段和

https://www.luogu.com.cn/problem/P2392 kkksc03考前临时抱佛脚

都是普及-的，我都打过

tommyyu

https://www.luogu.com.cn/training/211#problems

要善于使用官方题单

sfqxx

Ewan-Ahiouy 发表于 2023-8-18 13:10
你要学dp！好卷啊

https://www.luogu.com.cn/problem/P1002 过河卒

最后一题不是dp吗？我看看dp