动态规划关键点:

• 1.找到最优子结构

• 2.储存中间状态：

• 3.递推公式（美其名曰：状态转移方程或者 DP 方程）

动态规划 和 递归或者分治 没有根本上的区别（关键看有无最优的子结构）

共性：找到重复子问题差异性：最优子结构、中途可以淘汰次优解关键点

动态规划代码模版

// 状态定义
dp = new int [m+1][n+1];

// 初始状态
dp[0][0] = x;
dp[0][1] = y;
...

// DP状态推导
for i = 0; i <= n; ++i {
    for j = 0; j <= m; ++j {
        ...
        
        dp[i][j] = min{dp[i-1][j], dp[i][j-1], etc};  
    }
}

return dp[m][n]; // 最优解

用动态规划解这些题的基本步骤一般是：

• 1.找到重复子问题：例如 problem(i, j) = min(sub(i+1, j), sub(i+1, j+1)) + a[i,j]

• 2.定义状态数组：例如 f[i,j]

• 3.写出DP方程：例如 f[i,j] = min(f[i+1, j], f[i+1, j+1]) + a[i,j]

• 1.在做动态规划相关问题的时候注意空间复杂度，有很多时候可以优化到👉 O(1)
• 2.动态规划的题目难点在于找子问题，抽象出动态方程，只要这个能分析出来，代码还是比较好写的， 事实是DP方程确实难以抽象，多练，多想，急不得
• 3.最近看了一本书叫“异类”，10000小时的定律还是要有的，坚持吧