学习了一下动态规划算法，按正统的描述此类问题应该是具有“最优子结构”和“重叠子问题”的一大类问题，很多地方有非常规范的描述，这里不赘述。
简单的说，我的理解就是：
（1）大的思想是空间换时间
（2）首先分析是否“有规律”，然后定义一个状态，即为一维或二维子结点的状态，这个状态，往往是问题的解，但是也可能是隐含了解的数据，比如，求最长子串时，这个状态就是当前最长子串长度
（3）在定义状态的同时，也要分析转移方程，也叫递推公式，其实就是本结点和前面的那些已经处理过的结点之间，存在什么关系，往往是前面的结点中的最好的与当前结点存在非常特殊的关系。
（4）最后是要分析如何回溯求解，这就要配合转移方程，一般是倒序回溯，从后往前找满足转移方程的前一个结点
1 #include <stdlib.h> 2 #include <string> 3 #include <time.h> 4 5 using namespace std; 6 7 int min_of_three(int a, int b, int c) 8 { 9 if(a < b) 10 if(a < c) 11 return a; 12 else 13 return c; 14 else if(b < c) 15 return b; 16 else 17 return c; 18 } 19 20 int max_of_three(int a, int b, int c) 21 { 22 if(a > b) 23 if(a > c) 24 return a; 25 else 26 return c; 27 else if(b > c) 28 return b; 29 else 30 return c; 31 } 32 33 34 int main() 35 { 36 // ① 斐波纳契数列 37 // 问题定义：f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2); (n > 1)，输入n，求f(n) 38 { 39 // 状态定义：a[i] 是当前f(i) 40 // 转移方程：a[i] = a[i-1] + a[i-2] 41 const int n = 7; 42 int* aux = new int[n+1]; 43 aux[0] = 0; 44 aux[1] = 1; 45 for (int i = 2; i <= n; i++) 46 aux[i] = aux[i-1] + aux[i-2]; // 根据转移方程，求出每一步的状态 47 printf(">> 斐波纳契数列问题 "); 48 printf("n = %d ", n); 49 printf("result = %d ", aux[n]); 50 delete[] aux; 51 } 52 // ② 取硬币问题 53 // 问题定义：有币值为1、3、5的硬币，数量不限，输入n，求总币值为n时至少需要多少枚硬币 54 { 55 // 状态定义：a[i] 是当前币值下最小硬币数 56 // 转移方程：a[i] = 1 + min(a[i-1]:if(i>1), a[i-3]:if(i>3), a[i-5]:if(i>5)) 57 const int n = 18; 58 int* aux = new int[n+1]; 59 aux[0] = 0; 60 aux[1] = 1; 61 for (int i = 2; i <= n; i++) // 根据转移方程，求出每一步的状态 62 { 63 if(i < 3) 64 aux[i] = aux[i-1]+1; 65 else if(i < 5) 66 aux[i] = (aux[i-1]<aux[i-3]?aux[i-1]:aux[i-3])+1; 67 else 68 aux[i] = min_of_three(aux[i-1], aux[i-3], aux[i-5])+1; 69 } 70 printf(">> 取硬币问题 "); 71 printf("n = %d ", n); 72 printf("result = %d ", aux[n]); 73 74 // O(n)时间找出选择的硬币 75 printf("coins are : "); 76 for (int i = n, j = n; i >= 0; i--) 77 { 78 if(aux[j] - aux[i] == 1) 79 { 80 printf("%d ", j-i); 81 j = i; 82 } 83 } 84 printf(" "); 85 delete[] aux; 86 } 87 88 // ③ 最长递增子序列问题 89 // 问题定义：在一个字符串序列中，找出一个成递增状态的子序列，如314253，最长递增子序列为：123 90 { 91 // 状态定义：a[i] = 当前最长子序列长度 92 // 转移方程：a[i] = 1+max(a[j]:(s[j]<s[i]),j<i) 93 char* str = "AETBDTCSEEDFJEIFUGHEISDGUYUEGHSJDHDFJSDJFJKESJKJFSJFJLASDKJIWMJIFNVHISYIOSDFPEAQDMRSDYICNSHYUIYUTIIPUSDFEIVASDFWETIAZXETYLALZLQPKDPWQOWI"; 94 const int n = strlen(str); 95 int* aux = new int[n]; 96 memset(aux, 0, n*sizeof(int)); 97 for (int i = 0; i < n; i++) 98 { 99 for (int j = 0; j < i; j++) 100 if ((str[i] > str[j]) && (aux[i] < aux[j])) 101 aux[i] = aux[j]; 102 aux[i]++; 103 } 104 int len = 0; 105 for (int i = 0; i < n; i++) 106 if (aux[i] > len) 107 len = aux[i]; 108 printf(">> 最长递增子序列问题 "); 109 printf("str = %s ", str); 110 printf("result = %d ", len); 111 112 // 回溯数组，找出最长子序列 113 printf("substring is : "); 114 char* sub = new char[n]; 115 memset(sub, 0, n); 116 for (int i = n-1, j = 0; i >= 0 && len; i--) 117 if (aux[i] == len && len) // 找到满足长度条件，而且递减的下一个字符，存入缓冲区 118 sub[--len] = str[i]; 119 printf("%s ", sub); 120 delete[] aux; 121 delete[] sub; 122 } 123 // ④ 最长公共子序列问题 124 // 问题定义：两个字符串序列，找出他们公共的子序列中最长的那个，例如41253和42125，最长公共子序列为4125 125 { 126 // 状态定义：a[i][j] = str1[0:i]与str2[0:j]的最长公共子序列长度 127 // 转移方程：a[i][j] = max(a[i-1][j], a[i][j-1], a[i-1][j-1] + 1:if(str1[i] == str2[j])) 128 char* str1 = "1208347018256081230951823759028375830182837518END"; 129 char* str2 = "0827508375812398789738636472734865098127398572396239E0ERND7"; 130 const int m = strlen(str1); 131 const int n = strlen(str2); 132 int* aux = new int[m*n]; 133 memset(aux, 0, m*n*sizeof(int)); 134 for (int i = 0; i < m; i++) 135 for (int j = 0; j < n; j++) 136 { // 利用转移方程，计算每一步的最长子序列长度 137 if(i == 0 || j == 0) 138 aux[i*n+j] = str1[i]==str2[j]?1:0; 139 else 140 aux[i*n+j] = max_of_three(aux[(i-1)*n+j-1] + (str1[i]==str2[j]?1:0), aux[(i-1)*n+j], aux[i*n+j-1]); 141 } 142 printf(">> 最长公共子序列问题 "); 143 printf("str1 = %s str2 = %s ", str1, str2); 144 printf("result = %d ", aux[m*n-1]); 145 146 // 回溯矩阵，找出最长公共子序列 147 printf("substring is : "); 148 int len = aux[m*n-1]; 149 char* sub = new char[m]; 150 memset(sub, 0, m); 151 int i = m-1; 152 int j = n-1; 153 while (i&&j&&len) 154 { 155 while(i && (aux[(i-1)*n+j]==len)) // 找左上角，向上移动 156 i--; 157 while(j && (aux[i*n+j-1]==len)) // 找左上角，向左移动 158 j--; 159 // 到此处时，找到了左上角，锁定一个字符，该字符一定满足str1[i] == str2[j] 160 sub[--len] = str1[i]; // 因此可以不写条件：if(str1[i] == str2[j]) 161 162 i--;j--; // 向左上方移动一格 163 } 164 printf("%s ", sub); 165 delete[] aux; 166 delete[] sub; 167 } 168 // ⑤ 格子取数问题 169 // 问题定义，有一个m列n行的格子，其中一部分格子中放有数字，只能从左上角开始，向右或下方向移动至右下角，问：如何移动才能使经过的格子中的数之和最大 170 { 171 // 状态定义：a[i][j] = 从左上角到a[i][j]的最优路径所取数字之和 172 // 转移方程：a[i][j] = max(a[i-1][j], a[i][j-1]) + num[i][j] 173 const int m = 8; 174 const int n = 10; 175 int* num = new int[m*n]; 176 int* aux = new int[m*n]; 177 srand(time(0)); 178 for (int i = 0; i < m*n; i++) 179 num[i] = (rand()%5 == 0)?rand()%4+1:0; 180 181 aux[0] = num[0]; 182 for (int i = 1; i < m; i++) 183 aux[i*n] = aux[(i-1)*n] + num[i*n]; 184 for (int j = 1; j < n; j++) 185 aux[j] = aux[j-1] + num[j]; 186 for (int i = 1; i < m; i++) 187 for (int j = 1; j < n; j++) 188 aux[i*n+j] = (aux[(i-1)*n+j]>aux[i*n+j-1]?aux[(i-1)*n+j]:aux[i*n+j-1]) + num[i*n+j]; 189 190 printf(">> 格子取数问题 "); 191 printf("num = "); 192 for (int i = 0; i < m; i++) 193 { 194 for (int j = 0; j < m; j++) 195 printf(" %2d ", num[i*n+j]); 196 printf(" "); 197 } 198 printf(" "); 199 200 // 回溯数组，找出沿路所取的数字 201 printf("the path is : "); 202 int sum = aux[m*n-1]; 203 int* path = new int[m+n]; 204 memset(path, 0, (m+n)*sizeof(int)); 205 int i = m-1; 206 int j = n-1; 207 while (sum) 208 { 209 while(i && (aux[(i-1)*n+j]==sum)) // 找左上角，向上移动 210 i--; 211 while(j && (aux[i*n+j-1]==sum)) // 找左上角，向左移动 212 j--; 213 // 到此处时，找到了左上角，再比较哪个数最大 214 path[i+j] = num[i*n+j]; 215 sum -= num[i*n+j]; 216 if(aux[(i-1)*n+j]==sum) // 跳到前面一个最优路径上的格子里 217 i--; 218 else 219 j--; 220 } 221 for (int i = 0; i < m+n; i++) 222 if(path[i] != 0) 223 printf(" %d ", path[i]); 224 printf(" "); 225 delete[] aux; 226 delete[] path; 227 228 229 } 230 231 system("pause"); 232 return 0; 233 }
输出结果：
>> 斐波纳契数列问题 n = 7 result = 13 >> 取硬币问题 n = 18 result = 4 coins are : 3 5 5 5 >> 最长递增子序列问题 str = AETBDTCSEEDFJEIFUGHEISDGUYUEGHSJDHDFJSDJFJKESJKJFSJFJLASDKJIWMJIFNVHISYIOSDFPEAQDMRSDYICNSHYUIYUTIIPUSDFEIVASDFWETIAZXETYLALZLQPKDPWQOWI result = 26 substring is : ABCDEFGHIJKLMNOPQRSTUVWXYZ >> 最长公共子序列问题 str1 = 1208347018256081230951823759028375830182837518END str2 = 0827508375812398789738636472734865098127398572396239E0ERND7 result = 26 substring is : 20837581239879837583823END >> 格子取数问题 num = 0 0 4 0 0 0 2 2 4 2 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 4 2 0 0 0 0 0 1 0 1 0 3 the path is : 4 2 3 2 4 2 1 3 请按任意键继续. . .