专栏首页null的专栏数据结构和算法——动态规划

数据结构和算法——动态规划

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/google19890102/article/details/39736577

一、动态规划的思想

    动态规划(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));
	}

}

参考文献

  1. 动态规划算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构和算法——动态规划

    一、动态规划的思想     动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行...

    zhaozhiyong
  • 挑战数据结构与算法面试题——统计上排数在下排出现的次数

    题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 本题应该是一个确定的问题,即上排的是个数是题目中给定的...

    zhaozhiyong
  • 数据结构和算法——用动态规划求解最短路径问题

        在利用动态规划求解的过程中值得注意的就是是否包含最优子结构,简单来讲就是一个问题的最优解是不是包含着子问题的最优解。利用求解子问题的最优解最后得到整个问...

    zhaozhiyong
  • 经典中的经典算法 动态规划(详细解释,从入门到实践,逐步讲解)

    动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。

    233333
  • 数据结构和算法——动态规划

    一、动态规划的思想     动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行...

    zhaozhiyong
  • Java 8 中的拉姆达表达式是什么?

    拉姆达表达式就是一个匿名函数。在 C#中,拉姆达表达式是一个委托类型,因此拉姆达表达式可以赋值给一个委托变量。 Java 中,没有委托,Java 的设计者只能...

    水货程序员
  • hdu1014

    @坤的
  • POJ 刷题系列:1083. Moving Tables

    POJ 刷题系列:1083. Moving Tables 传送门:POJ 1083. Moving Tables 题意: 一条走廊,两栏房间。搬运工每次从房价...

    用户1147447
  • P3809 【模版】后缀排序

    题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

    attack
  • 剑指OFFER之重建二叉树(九度OJ1385)

    题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

    用户1154259

扫码关注云+社区

领取腾讯云代金券