算法概述其实就是在分治算法的基础上加上一个数组记录子问题的最优解防止子问题被重复求解算法的基本思想与分治算法类似也是将待求解的问题划分为若干子问题按划分的顺序求解子问题。前一个子问题的解为后一子问题的求解提供了有用的信息最优子结构。在求解任一子问题时列出各种可能的局部解通过决策保留那些有可能达到最优的局部解丢弃其他局部解一次解决各个子问题最后求出原问题的最优解算法的经典问题硬币选择问题有135面值的硬币求组成某一特定值所需的最少硬币假设特定值为11问题分析代码实现int arr[] { 1,3,5 }; int val 11; int dp(int dp1[],int n) { if (dp1[n] 0) return dp1[n]; if (n 1 || n 3 || n 5) { dp1[n] 1; return 1; } if (n 2 || n 4) { dp1[n] 2; return 2; } else { int n1 dp(dp1, n - 1) 1; int n2 dp(dp1, n - 3) 1; int n3 dp(dp1, n - 5) 1; int min1 min(n1, n2); int min2 min(min1, n3); dp1[n] min2; return dp1[n]; } } int main() { int dp1[12] { 0 }; int n 11; int ret dp(dp1,n); cout ret endl; return 0; } 非递归写法 dp[0]0 dp[1]1 dp[2]2 dp[3]1dp[3-1]1dp[2]3 || dp[3]1dp[3-3]1 dp[3]1 dp[4]1dp[4-1]1dp[3]2 || dp[4]1dp[4-3]1dp[1]2 dp[4]2 int arr[] { 1,3,5 }; int main() { int n 11; int dp[12] { 0 }; for (int i 1; i n; i) { dp[i] i; for (int j 0; j 3; j) { if (i arr[j] (1 dp[i - arr[j]] dp[i])) { dp[i] 1 dp[i - arr[j]]; } } } cout dp[11]; return 0; }LCS最长公共子序列给定两个子序列str1helloworldstr2: helword求两个子序列最长公共子序列问题分析代码实现//LCS最长公共子序列 //str1:helloworld //str2:helword //从最后一个元素开始比较 str1.size(),str2.size() // 不相等:max(str1.size()-1,str2.size()-1); // 相等str1.size()-1,str2.size()-1 //动态规划法其实就是将两个序列比较的结果存放在一个dp数组中但是此问题既需要存放两个数组的长度也需要存放两个数组 //的比较结果所以dp数组为二维数组 #includestring #includevector string str1 helloworld; string str2 helword; //如果想要打印最长公共子序列当str1.size()-1与str2.size()-1时其实是遇到了公共字母那么就需要记录下来。 //那么规定当str1.size()-1与str2.size()-1时记录为1str1.size()与str2.size()-1记录为2str1.size()-1与str2.size()记录为3 //在开辟一个二维数组path用来记录这些数字其实就是两个序列走的路径根据path就可以找到对应的子序列 vectorvectorintdp(str1.size(),vectorint(str2.size(),-1)); vectorvectorintpath(str1.size(), vectorint(str2.size(), 0)); int LCS(int i, int j) { if (i 0 || j 0) { return 0; } if (dp[i][j] 0) { return dp[i][j]; } if (str1[i] str2[j]) { path[i][j] 1; dp[i][j] LCS(i - 1, j - 1)1; return dp[i][j]; } else { int len1 LCS(i - 1, j); int len2 LCS(i, j - 1); if (len1 len2) { path[i][j] 3; } else { path[i][j] 2; } dp[i][j] max(len1, len2); return dp[i][j]; } } void print_path(int i, int j) { if (i 0 || j 0) { return; } if (path[i][j] 1) { print_path(i - 1, j - 1); cout str1[i]; } else if (path[i][j] 2) { print_path(i, j - 1); } else { print_path(i - 1, j); } } int main() { coutLCS(str1.size()-1, str2.size()-1)endl; print_path(str1.size() - 1, str2.size() - 1); return 0; }0-1背包问题vectorintw { 8,6,4,2,5 };//物品的重量,5vectorintv { 6,4,7,8,6 };//物品的价值,5int c 12;//背包的容量//背包的容量为12求背包中的最大价值问题分析代码实现vectorintw { 8,6,4,2,5 };//物品的重量,5 vectorintv { 6,4,7,8,6 };//物品的价值,5 int c 12;//背包的容量 //背包的容量为12求背包中的最大价值 //动态规划算法 // 在dp数组中要存放的量有背包的容量所选物品的重量和已选物品的价值 // dp[n][m]选择范围是第n个物品到最后一个物品中物品组合的最大价值,行表示选择范围是第n个物品到最后一个物品列表示背包的容量 vectorvectorintdp(w.size(), vectorint(13, 0)); void dp1(int i,int c) { if (i 0||c 13 ) { return; } if (w[i] c) { dp[i][c] dp[i 1][c]; dp1(i,c1); } else { dp[i][c] max(dp[i 1][c], v[i] dp[i 1][c-w[i]]); dp1(i,c1); } i--; dp1(i, c); } void print() { int ca c; int val 0; for (int i 0; i w.size()-1; i) { if (dp[i][c] ! dp[i 1][c]) { cout w[i] ; ca - w[i]; val v[i]; } } if (dp[w.size() - 1][c] 0) { cout w[w.size() - 1] endl; val v[w.size() - 1]; } cout val endl; } int main() { for (int i 1; i 13; i) { if (w[w.size() - 1] i) { dp[w.size() - 1][i] 0; } else { dp[w.size() - 1][i] v[v.size() - 1]; } } for (int i w.size() - 1 - 1; i 0; i--) { for (int j 1; j 13; j) { if (w[i] j) { dp[i][j] dp[i 1][j]; } else { dp[i][j] max(dp[i 1][j], v[i] dp[i 1][j - w[i]]); } } } print(); //dp1(w.size() - 2,1); for (auto a : dp) { for (auto b : a) { cout b ; } cout endl; } }