动态规划问题解决方法及示例

什么是动态规划

动态规划是求解决策过程最优化的数学方法。如果一个问题可以分解成若干个子问题&＃xff0c;并且子问题之间还有重叠的更小的子问题&＃xff0c;就可以考虑用动态规划来解决这个问题。

应用动态规划之前要分析能否把大问题分解成小问题&＃xff0c;分解后的每个小问题也存在最优解。如果将小问题的最优解组合起来能够得到整个问题的最优解&＃xff0c;那么就可以使用动态规划解决问题。

可以应用动态规划求解的问题主要由四个特点&＃xff1a;
1. 问题是求最优解
2. 整体问题的最优解依赖于各个子问题的最优解
3. 大问题分解成若干小问题&＃xff0c;这些小问题之间还有相互重叠的更小的子问题
4. 从上往下分析问题&＃xff0c;从下往上求解问题

分析

例&＃xff1a;给定数组arr&＃xff0c;arr中所有的值都为正数且不重复。每个值代表一种面值的货币&＃xff0c;每种面值的货币可以使用任意张&＃xff0c;再给定一个整数aim代表要找的钱数&＃xff0c;求换钱有多少种方法。

思路及优化方法&＃xff1a;

暴力搜索方法

arr&＃61;{5、10、25、1}&＃xff0c;aim&＃61;1000

1、用0张5元的货币&＃xff0c;让[10,25,1]组成剩下的1000&＃xff0c;最终方法数记为res1
2、用1张5元的货币&＃xff0c;让[10,25,1]组成剩下的995&＃xff0c;最终方法数记为res2
3、用2张5元的货币&＃xff0c;让[10,25,1]组成剩下的990&＃xff0c;最终方法数记为res3
……
201、用200张5元的货币&＃xff0c;让[10,25,1]组成剩下的0&＃xff0c;最终方法数记为res201

最终结果为res1&＃43;res2&＃43;…&＃43;res201。

定义递归函数&＃xff1a;int p1(arr, index, aim),返回用arr[index]至arr[N-1]的货币面值组成面值aim的方法数。

public class DynamicProgramming {public int coins1(int[] arr, int aim) {if (arr &＃61;&＃61; null || arr.length &＃61;&＃61; 0 || aim <0) {return 0;}return process(arr, 0, aim);}/*** 即上述p1方法*/public int process(int[] arr, int index, int aim) {int res &＃61; 0;if (arr.length &＃61;&＃61; index) {return (aim &＃61;&＃61; 0 ? 1 : 0);}for (int i &＃61; 0; arr[index] * i <&＃61; aim; i&＃43;&＃43;) {// arr[index]选i张时&＃xff0c;让剩下的货币组成aim-arr[index]*i面额的方法数&＃xff0c;即res_i// 总的方法数即为res_0&＃43;res_1&＃43;...&＃43;res_(aim/arr[index])res &＃43;&＃61; process(arr, index &＃43; 1, aim - arr[index] * i);}return res;}
}


优点&＃xff1a;简单方便
缺点&＃xff1a;重复计算导致多余的递归&＃xff0c;最终导致效率低下

如果已经使用0张5元和1张10元的情况下&＃xff0c;后续将求&＃xff1a;process(arr, 2, 990);
但是如果已经使用了2张5元和0张十元时&＃xff0c;也将要求&＃xff1a;process(arr, 2, 990);
就会造成重复计算。

记忆搜索方法

思路&＃xff1a;使用HashMap记录计算结果。

public class DynamicProgramming {/*** 二维数组map[i][j]的结果代表process(arr, i, j)的返回结果*/private int[][] map;public int coins1(int[] arr, int aim) {if (arr &＃61;&＃61; null || arr.length &＃61;&＃61; 0 || aim <0) {return 0;}map &＃61; new int[arr.length &＃43; 1][aim &＃43; 1];return process(arr, 0, aim);}/*** 即上述p1方法*/public int process(int[] arr, int index, int aim) {int res &＃61; 0;if (arr.length &＃61;&＃61; index) {return (aim &＃61;&＃61; 0 ? 1 : 0);}for (int i &＃61; 0; arr[index] * i <&＃61; aim; i&＃43;&＃43;) {int mapValue &＃61; map[index &＃43; 1][aim - arr[index] * i];/**mapValue为0表示还没有往当前map中对应位置保存值*/if (mapValue !&＃61; 0) {res &＃43;&＃61; (mapValue &＃61;&＃61; -1 ? 0 : mapValue);} else {// arr[index]选i张时&＃xff0c;让剩下的货币组成aim-arr[index]*i面额的方法数&＃xff0c;即res_i// 总的方法数即为res_0&＃43;res_1&＃43;...&＃43;res_(aim/arr[index])res &＃43;&＃61; process(arr, index &＃43; 1, aim - arr[index] * i);}}//计算完毕&＃xff0c;将计算结果保存至map&＃xff0c;由于res可能为0&＃xff0c;这里当map&＃61;0时表示map中的值还没有计算&＃xff0c;等于-1时表示当前值为0map[index][aim] &＃61; (res &＃61;&＃61; 0 ? -1 : res);return res;}public static void main(String[] args) {int[] arr &＃61; {5, 10, 25, 1};int cnt &＃61; new DynamicProgramming().coins1(arr, 1000);System.out.println(cnt);}
}

动态规划方法

如果arr长度为N&＃xff0c;生成行数为N&＃xff0c;列数为aim&＃43;1的矩阵dp。dp[i][j]的含义是在使用arr[0…i]货币的情况下&＃xff0c;组成钱数j有多少种方法。

举例&＃xff1a;arr[0]&＃61;5

求每一个位置都需要枚举&＃xff0c;时间复杂度为O(aim)。dp一共有N*(aim&＃43;1)个位置&＃xff0c;对于每个位置要枚举该位置上一行左侧&＃xff08;包括正上&＃xff09;的所有位置的值&＃xff0c;因此总体的时间复杂度为O(N*aim^2)。

code&＃xff1a;

public class DynamicProgramming {private int[][] dp;public int coins(int[] arr, int aim) {dp &＃61; new int[arr.length][aim &＃43; 1];for (int i &＃61; 0; i 0] &＃61; 1;}for (int i &＃61; 0; i 1; i&＃43;&＃43;) {if (i % arr[0] &＃61;&＃61; 0) {dp[0][i] &＃61; 1;}}for (int i &＃61; 1; i for (int j &＃61; 1; j 1; j&＃43;&＃43;) {calDp(arr, i, j); //计算dp[i][j]}}return dp[arr.length - 1][aim];}private int calDp(int[] arr, int i, int j) {int dp_ij &＃61; 0;for (int m &＃61; 0; j - m * arr[i] >&＃61; 0; m&＃43;&＃43;) {dp_ij &＃43;&＃61; dp[i - 1][j - m * arr[i]];}dp[i][j] &＃61; dp_ij;return dp_ij;}public static void main(String[] args) {int[] arr &＃61; {5, 10, 25, 1};int cnt &＃61; new DynamicProgramming().coins(arr, 1000);System.out.println(cnt);}
}


上述算法的时间复杂度为O(N*aim^2)。

记忆搜索方法与动态规划方法的联系

1. 记忆搜索方法就是某种形态的动态规划方法
2. 记忆搜索方法不关心到达某一个递归过程的路径&＃xff0c;只是单纯的对计算过的递归过程进行记录&＃xff0c;避免重复的递归过程。
3. 动态规划的方法则是规定好每一个递归过程的计算顺序&＃xff0c;依次进行计算&＃xff0c;后面的计算过程严格依赖前面的计算过程。
4. 两者都是空间换时间的方法&＃xff0c;也都有枚举的过程&＃xff0c;区别在于动态规划规定计算顺序&＃xff0c;而记忆搜索不用规定。

再谈什么是动态规划

1. 其本质是利用申请的空间来记录每一个暴力搜索的计算结果&＃xff0c;下次要用结果的时候直接使用&＃xff0c;而不再进行重复的递归过程。
2. 动态规划规定每一种递归状态的计算顺序&＃xff0c;依次进行计算。

对上述动态规划问题的优化

因为由上述分析可以dp[i][j]&＃61;dp[i-1][j]&＃43;dp[i-1][j-1*arr[i]]&＃43;…&＃xff0c;即在上述图中所示&＃xff0c;dp[i][j]的值即为上一行的列下标为j-k*arr[i]且>&＃61;0&＃xff0c;k&＃61;0&＃xff0c;1&＃xff0c;2…的值之和。

而dp[i][j-1*arr[i]]的值同理即为dp[i-1][j-1*arr[i]] &＃43; dp[i-1][j-2*arr[i]] &＃43; …

因此dp[i][j] &＃61; dp[i-1][j] &＃43; dp[i][j-arr[i]]。
经过这样化简后的动态规划方法时间复杂度为O(N*aim)。

优化后的代码&＃xff1a;

public class DynamicProgramming {private int[][] dp;public int coins(int[] arr, int aim) {dp &＃61; new int[arr.length][aim &＃43; 1];for (int i &＃61; 0; i 0] &＃61; 1;}for (int i &＃61; 0; i 1; i&＃43;&＃43;) {if (i % arr[0] &＃61;&＃61; 0) {dp[0][i] &＃61; 1;}}for (int i &＃61; 1; i for (int j &＃61; 1; j 1; j&＃43;&＃43;) {calDp(arr, i, j);}}return dp[arr.length - 1][aim];}private void calDp(int[] arr, int i, int j) {// 在这里进行优化if ((j - arr[i]) >&＃61; 0) {dp[i][j] &＃61; dp[i - 1][j] &＃43; dp[i][j - arr[i]];return;}int dpIj &＃61; 0;for (int m &＃61; 0; j - m * arr[i] >&＃61; 0; m&＃43;&＃43;) {dpIj &＃43;&＃61; dp[i - 1][j - m * arr[i]];}dp[i][j] &＃61; dpIj;}public static void main(String[] args) {int[] arr &＃61; {5, 10, 25, 1};int cnt &＃61; new DynamicProgramming().coins(arr, 1000);System.out.println(cnt);}
}

动态规划方法的关键点

1、最优化原理&＃xff0c;也就是最优子结构性质。这指的是一个最优化策略具有这样的性质&＃xff1a;不论过去状态和决策如何&＃xff0c;对前面的决策所形成的状态而言&＃xff0c;余下的诸决策必须构成最优策略。简单来说就是一个最优化策略的子策略总是最优的&＃xff0c;如果一个问题满足最优化原理&＃xff0c;就称其具有最优子结构性质。

2、无后效性。指的是某状态下决策的收益&＃xff0c;只与状态和决策相关&＃xff0c;与到达该状态的方式无关。

3、子问题的重叠性&＃xff0c;动态规划将原来具有指数级时间复杂度的暴力搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余&＃xff0c;这时动态规划算法的根本目的。

几个例题

例题1&＃xff08;LeetCode&＃xff09;

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:

Input: "cbbd"
Output: "bb"


方法一&＃xff1a;动态规划

code&＃xff1a;

class Solution {boolean dp[][];public String longestPalindrome(String s) {dp &＃61; new boolean[s.length()][s.length()];for (int i &＃61; 0; i for (int j &＃61; 0; j if (i > j) {continue;}if (i &＃61;&＃61; j) {dp[i][j] &＃61; true;} else if (j &＃61;&＃61; (i &＃43; 1)) {dp[i][j] &＃61; (s.charAt(i) &＃61;&＃61; s.charAt(j));}}}for (int i &＃61; s.length() - 1; i >&＃61; 0; i--) {for (int j &＃61; 0; j if (i >&＃61; j || j &＃61;&＃61; (i &＃43; 1)) {continue;}dp[i][j] &＃61; (dp[i &＃43; 1][j - 1] && s.charAt(i) &＃61;&＃61; s.charAt(j));}}int maxLength &＃61; 0, maxI &＃61; 0, maxJ &＃61; 0;for (int i &＃61; 0; i for (int j &＃61; 0; j if (i > j) {continue;}if (dp[i][j] && (j - i &＃43; 1) > maxLength) {maxLength &＃61; j - i &＃43; 1;maxI &＃61; i;maxJ &＃61; j;}}}return s.substring(maxI, maxJ &＃43; 1);}
}

方法二&＃xff1a;Expand Around Center

方法三&＃xff1a;Manacher算法

Manacher算法解决