一、动态规划的思想
动态规划(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
参考文献
- 动态规划算法
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
解题思路:这是一道很裸的二维树状数组 AC: #include #include #define N 1100 int c[N][N],n,arr[N][N]; int lowbit(int x) { return x&(-x); } void upd…