1.1. 基本结构

动态规划(dynamic programming) 是运筹学的一个分支,是求解决策过程(decision process)中最优化的数学方法。

  • 起源:在研究多阶段决策过程(multi-step decision process)的优化问题时,提出的最优性原理(principle of optimality),把多阶段过程转化为单阶段问题,逐个求解。
  • 应用领域:经济管理、生产调度、工程技术和最优控制。
  • 局限:主要是用于求解“分阶段”的动态过程的优化问题。
  • 经典问题:背包问题
  • 比较:
    • 贪婪:永远局部最优
    • 递归:重复计算
    • DP:记录局部最优子结构/多种记录值

1.1.1. 基本概念

  • 阶段step:它是对整个过程的划分,通常会根据时间或者空间顺序进行分阶段。
  • 状态state:它表示每个阶段开始时过程所处的自然状况,它描述了过程的特征并且无后效性。
    • 无后效应:与之前的状态无关。
    • 状体变量state variable:用于描述状态的变量。
  • 决策decision:当一个阶段状态确定后,可以作出各种选择从而演变到下一阶段的某种状态,称为决策。
  • 策略 policy:决策组成的序列称为策略。
  • 状态转移方程 equation of state transition :用于描述某阶段的状态和决策与下阶段状态的关系。

1.1.2. 基本思想-- 多阶段决策。

1.1.3. 实现步骤

  1. 递推 / 递归+记忆性
  2. 动态规划:分治+最优子结构(每次都淘汰掉次优的状态。例如step(n) = Max(step(n-1)+n,step(n-2)),淘汰了小的那一个)

1.1.4. 递归模板

public void recur(int level, int param) { 
  // terminator 
  if (level > MAX_LEVEL) { 
    // process result 
    return; 
  } 
  // process current logic 
  process(level, param); 
  // drill down 
  recur( level: level + 1, newParam); 
  // restore current status 
}

1.2. 常见面试题

1.2.1. 70. 爬楼梯

当前楼层的种类数,等于前一步和前两步的总和。因为每次只能走一步或者两步。

// 1. 递归
public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}
// 2. 递归+记忆性
Map<Integer, Integer> map = new HashMap<>();
public int climbStairs(int n) {
    if (n == 1) {
        map.put(1, 1);
        return 1;
    } else if (n == 2) {
        map.put(2, 2);
        return 2;
    }
    int step1 = map.containsKey(n - 1) ? map.get(n - 1) : climbStairs(n - 1);
    int step2 = map.containsKey(n - 2) ? map.get(n - 2) : climbStairs(n - 2);
    map.put(n, step2 + step1);
    return step2 + step1;
}
// 3. 递推
public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        // 0,1 分别表示第一级和第二级
        int[] result = new int[n];
        result[0] = 1;
        result[1] = 2;
        for (int i = 2; i < n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n-1];
    }
}

1.2.2. 72. 编辑距离

参考于这个文章

public int minDistance(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();
    // 如果有一个等于0,则是n+m(将另一个完全替换)。
    if (n * m == 0) {
        return n + m;
    }
    int[][] arr = new int[n + 1][m + 1];
    for (int i = 0; i < n + 1; i++) {
        arr[i][0] = i;
    }
    for (int i = 0; i < m + 1; i++) {
        arr[0][i] = i;
    }
    // 假设现在是 HOR与RO比较, left表示HOR与R的距离,down表示HO与RO的距离,slash表示HO与R的距离。
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            int left = arr[i - 1][j] + 1;
            int down = arr[i][j - 1] + 1;
            int slash = arr[i - 1][j - 1];
            if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                slash += 1;
            }
            arr[i][j] = Math.min(left, Math.min(down, slash));
        }
    }
    return arr[n][m];
}

1.2.3. 120. 三角形最小路径和

每个数都等于当前数加上,上一行可以加的最小值的数。

public int minimumTotal(List<List<Integer>> triangle) {
    int len = (triangle.size() + 1) * triangle.size() / 2;
    int[] ans = new int[len];
    ans[0] = triangle.get(0).get(0);
    int k = 1;
    for (int i = 1; i < triangle.size(); i++) {
        List<Integer> list = triangle.get(i);
        int size = list.size();
        for (int j = 0; j < size; j++, k++) {
            // 先处理最左边和最右边
            if (j == 0) {
                // 处理最左侧的,减去上一行的长度
                ans[k] = ans[k - (size - 1)] + list.get(j);
            } else if (j == size - 1) {
                // 处理最右侧的,减去本行的长度
                ans[k] = ans[k - size] + list.get(j);
            } else {
                ans[k] = Math.min(ans[k - size], ans[k - size + 1]) + list.get(j);
            }
        }
    }
    // 找到最小值
    int min = Integer.MAX_VALUE;
    for (int i = len-triangle.size(); i < len; i++) {
        min =Math.min(ans[i],min);
    }
    return min;
}

1.2.4. 121. 买卖股票的最佳时机

1.2.5. 122. 买卖股票的最佳时机 II

1.2.6. 123. 买卖股票的最佳时机 III

1.2.7. 152. 乘积最大子序列

1.2.8. 188. 买卖股票的最佳时机 IV

1.2.9. 300. 最长上升子序列

1.2.10. 309. 最佳买卖股票时机含冷冻期

1.2.11. 322. 零钱兑换

// 递归
public int coinChange(int[] coins, int amount) {
    // 终结条件
    if (amount == 0) {
        return 0;
    }
    // 初始化结果,进行操作
    int ans = Integer.MAX_VALUE; 
    for (int coin : coins) {
        if (amount - coin < 0) {
            continue;
        } else {
            int sub = coinChange(coins, amount - coin);
            if (sub == -1) {
                continue;
            } else {
                ans = Math.min(ans, sub + 1);
            }
        }
    }
    return ans == Integer.MAX_VALUE ? -1 : ans;
}
// 2.递推
public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    int[] res = new int[amount+1];
    for (int i = 1; i < res.length; i++) {
        int cost = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (i - coin >= 0 && res[i - coin] != Integer.MAX_VALUE) {
                cost = Math.min(res[i - coin] + 1, cost);
            }
        }
        res[i] = cost;
    }
    return res[amount]==Integer.MAX_VALUE?-1:res[amount];
}

1.2.12. 714. 买卖股票的最佳时机含手续费

results matching ""

    No results matching ""