动态规划

动态规划各种类型题目的总结

本科算法课老师说动态规划是为了优化递归导致的重复问题的求解，使用空间换取重复计算的时间开销，也有人将其称为记忆化搜索等，现尝试将动态规划分为几种模式

模式

到达目标的最大最小路径
达到目标不同的方式的总数
合并区间
字符串动态规划问题
做决定

1.到达目标的最大(最小)路径

问题描述

给一个目标去寻找最大(最小)的消耗/路径/到达路径

方法

在当前状态之前，寻找所有路径中最大最小的路径，并与当前状态值进行加减

1	routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

为目标中所有值生成最优解，并返回目标值

自顶而下的解法

for (int j = 0; j < ways.size(); ++j) {
    result = min(result, topDown(target - ways[j]) + cost/ path / sum);
}
return memo[/*state parameters*/] = result;

自底而上的解法

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] = min(dp[i], dp[i - ways[j]] + cost / path / sum) ;
       }
   }
}
 
return dp[target]

2.达到目标的不同方式的总数

问题描述

给出一个目标，找到达到目标的所有方式的总数

方法

统计到达当前状态之前所有可能的路径

1	routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] += dp[i - ways[j]];
       }
   }
}
 
return dp[target]

3.区间合并

给定一组数字，考虑当前数字以及从左侧，右侧能够得到的最优数字，找到问题的最佳解决方案

方法

找到每个区间的所有最佳解决方案并返回最佳答案

1 2	// from i to j dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]

从左侧或者右侧找到最佳答案，并添加当前位置的解

4.字符串上的DP

问题描述

该模式的问题描述可能差距较大，但大多数时候会给出两个字符串，且两字符串长度不大

给两个字符串s1与s2返回some result

方法

这种模式下的问题，大多需要一个时间复杂度为n2的解法

// i - indexing string s1
// j - indexing string s2
for (int i = 1; i <= n; ++i) {
   for (int j = 1; j <= m; ++j) {
       if (s1[i-1] == s2[j-1]) {
           dp[i][j] = /*code*/;
       } else {
           dp[i][j] = /*code*/;
       }
   }
}

或者给出一个字符串

for (int l = 1; l < n; ++l) {
   for (int i = 0; i < n-l; ++i) {
       int j = i + l;
       if (s[i] == s[j]) {
           dp[i][j] = /*code*/;
       } else {
           dp[i][j] = /*code*/;
       }
   }
}

5.取舍问题(当前元素取还是不取)

这种问题的一般模式是需要结合问题的陈述，决定是否需要使用当前状态，需要基于当前状态做出决定

问题描述

给定一组值，通过选择或者忽略当前值的找到答案

解法

如果使用当前值，则忽略当前值之前的结果，反之，如果需要忽略当前值，则需要使用值的当前结果

// i - indexing a set of values
// j - options to ignore j values
for (int i = 1; i < n; ++i) {
   for (int j = 1; j <= k; ++j) {
       dp[i][j] = max({dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1]});
       dp[i][j-1] = max({dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i]});
   }
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。