讨论/算法和数据结构/如何学习动态规划?/
如何学习动态规划?

或者说那里有好的学习资源,本人遇到动态规划难一点的题目就不会求转换方程了,求大佬解答。
很多时候直到要用动态规划,但是自己弄不出核心的转换方程和 dp 对应的含义。
动态规划学了好久了,一直弄不明白。只要是没有见过的题就不知道怎么写状态转移方程,怎么循环,以及怎么处理细节。
希望大家分享一下自己看到的关于动态规划不错的资料,题目 / 文章 / 视频都可以 ~。谢谢!~

展开讨论

最重要的是弄清楚 dp[] 数组你需要代表的意思状态转移方程 比如说 比较经典的背包问题
dp[i][j] 代表的是在选择i种物品的时候并且承重为j的时候,可以得到的最大价值。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); 是这个的状态转移方程

for (int i = 1; i <= 4; i++) 
{
    for (int j = 1; j <= maxW; j++)
    {
        if (j < w[i])				//当你的背包容量不能放下当前w[i]物品的时候 
            dp[i][j] = dp[i - 1][j];	//此时dp的应该是dp[i-1]物品的价值
        else
        {
        //当你可以放下w[i]物品的时候,你需要进行一次比较,放弃存放物品背包的价值大,还是当你放入w[i]物品后计算出你目前背包的价值大 dp[i - 1][j - w[i]] + v[i] 此时应该是让dp[i-1][j - w[i]]的价值最大,依次往前计算,最后可以得到一个需要的价值最大值。
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }
}
1
展开全部 5 讨论