动态规划

判断动态规划

Wikipedia 定义：它既是一种数学优化的方法，同时也是编程的方法。

1. 是数学优化的方法——最优子结构

动态规划是数学优化的方法指，动态规划要解决的都是问题的最优解。而一个问题的最优解是由它的各个子问题的最优解决定的。

由此引出动态规划的第一个重要的属性：最优子结构（Optimal Substructure)。

一般由最优子结构，推导出一个状态转移方程 f(n)，就能很快写出问题的递归实现方法。

2. 是编程的方法——重叠子问题

动态规划是编程的方法指，可以借助编程的技巧去保证每个重叠的子问题只会被求解一次。

引出了动态规划的第二个重要的属性：重叠子问题（Overlapping Sub-problems）。

一、两种思路

1、第一种思路模板是一个一维的 dp 数组：

int n = array.length;
int[] dp = new int[n];

for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        dp[i] = 最值(dp[i], dp[j] + ...)
    }
}

2、第二种思路模板是一个二维的 dp 数组：

int n = arr.length;
int[][] dp = new dp[n][n];

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (arr[i] == arr[j]) 
            dp[i][j] = dp[i][j] + ...
        else
            dp[i][j] = 最值(...)
    }
}