版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1395612
动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行求解,最终得到整个问题的解。有人在想这样的方式和分治法的求解很像。
在动态规划法中,与其对交叠的子问题一次一次求解,不如对每个较小的子问题只求解一次并把结果记录在表中,这样就能从表中得到原始问题的解。举个简单的例子,对于菲波那切数列来说:
对于这样的递推式,可以把一个复杂的问题分解成几个非独立的子问题,我们可以采用的方式是记录每一组值,如斐波那契数列的值依次是0,1,1,2,3,5,...。而不需要重复去计算。
二项式系数问题是一个求解
的问题。我们有如下的递推式:
要计算
的值,我们需要记录
到
之间的值。动态规划的核心思想就是要找到这样的递推式,然后构建这样的存储空间去记录中间的值,避免重复计算。最简单的方式是利用数组去记录。
如上的问题可以用下面的Java代码实现:
package org.algorithm.dynamicprogramming;
/**
* 利用动态规划的思想去求解二项式系数的问题
*
* @author dell
*
*/
public class CalculateDemo {
/**
* 用动态规划计算C(n,k)
*
* @param n为二项式的参数
* @param k为二项式的参数
* @return C(n,k)的值
*/
public static int calBinomial(int n, int k) {
int C[][] = new int[n+1][k+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= minValue(i, k); j++) {
if (j == 0 || j == i) {
C[i][j] = 1;
} else {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
}
return C[n][k];
}
// 返回较小的值
public static int minValue(int i, int k) {
return (i <= k ? i : k);
}
public static void main(String args[]) {
int n = 10;
int k = 5;
System.out.println(calBinomial(n, k));
}
}
参考文献