不会飞的章鱼

熟能生巧，勤能补拙；念念不忘，必有回响。

算法训练营-动态规划的实现及关键点

发表于 更新于 分类于
本文字数： 300 阅读时长 ≈ 1 分钟

动态规划-Dynamic Programming

1，wiki定义
2，in a recursive manner
3，Divide & Conquer + Optimal substructure——分治+最优子结构

关键点

  • 动态规划和递归或者分治没有根本区别（关键看有无最优的子结构）
  • 共性：找到重复子问题
  • 差异性：最优子结构、中途可以淘汰次优解

顺推模板

1
2
3
4
5
6
7
8
9
10
fuction DP():
    dp = [][] #二维情况

    for i = 0..M {
        for j = 0..N {
            dp[i][j] = _Fuction(dp[i'][j']...)
        }
    }

    return dp[M][N]
------ 本文结束------
如果本篇文章对你有帮助，可以给作者加个鸡腿~(*^__^*)，感谢鼓励与支持！