例一:计算二项式系数:
在排列组合里面,我们有下面的式子(很容易用组合的定义来证明):
这个式子将C(n , k)的计算问题表述为了(问题描述)C(n-1 , k -1)和C(n -1, k)两个较小的重叠子问题。
/*
* 用动态规划算法计算C(n,k)
* 输入:一对非负整数n>=k>=0
* 输出:C(n,k)的值
*/
import java.util.*;
public class Binomial {
int C[][];
int Computing(int n,int k){
C = new int[n+1][n+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=Math.min(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 void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("请输入n:");
int n = in.nextInt();
System.out.println("请输入k(0<=k<=n):");
int k = in.nextInt();
Binomial b=new Binomial();
System.out.println("C["+n+","+k+"] = "+b.Computing(n, k));
for(int i = 0;i <= 8;i++)
System.out.println("C" + "[" + 8 + "," + i + "]" + " ———— " +b.Computing(8,i));
}
}
运行:
C:\java>java Binomial
请输入n:
5
请输入k(0<=k<=n):
5
C[5,5] = 1
C[8,0] ———— 1
C[8,1] ———— 8
C[8,2] ———— 28
C[8,3] ———— 56
C[8,4] ———— 70
C[8,5] ———— 56
C[8,6] ———— 28
C[8,7] ———— 8
C[8,8] ———— 1
例二:斐波那契数列(动规实现)
无穷数列1,1,2,3,5,8,13,21,34,55,…,被称为Fibonacci数列。它可以递归地定义为:
2 程序实现
缓存是为了减少重复计算。
import java.util.HashMap;
import java.util.Map;
public class FibonacciUtil {
static Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
public static int fib(int n) {
if (n == 0 || n == 1)
return 1;
if (null != cache.get(n))
return cache.get(n);
int ret = fib(n - 1) + fib(n - 2);
cache.put(n, ret);
return ret;
}
public static void listFib(int n){
for(int i=1;i<n;i++){
System.out.print(fib(i)+",");
}
}
public static void main(String[] args) {
listFib(10);
}
}
若求问题的唯一解(最优解),先分解成为子问题,而子问题的解也是唯一的(最优的)。子问题有重叠,为了减少重复计算,缓存重叠部分计算结果;
这两点也正是动规算法的精髓。实际上,这个例子是动规算法最简单的一个实例。
下载源代码。
- 大小: 7.5 KB
- 大小: 8.6 KB
分享到:
相关推荐
标题 "动态规划算法学习十例之八" 暗示了我们将探讨动态规划这一重要的算法概念,特别是通过一个具体的例子——Matrix Chain Multiplication(矩阵链乘法)来深入理解。动态规划是一种解决复杂问题的有效方法,它...
在这个“动态规划算法学习十例之七”的主题中,我们将聚焦于一个具体的动态规划问题——最长公共子序列(Longest Common Subsequence,简称LCS)。这个问题在计算机科学中具有很高的实用价值,尤其是在比较和分析...
在这个“动态规划算法学习十例之九”的主题中,我们将聚焦于如何通过DP来解决实际问题。尽管描述部分没有提供具体的实例,但从标题来看,我们可以推测这是一个关于动态规划应用的系列教程的第九个例子。 动态规划的...
在这个主题“动态规划算法学习十例之六”中,我们将探讨如何利用动态规划方法来解决实际问题。博文链接虽然未提供具体内容,但我们可以根据提供的文件名推测讨论的是一个具体的编程实例。 `Main.java`通常是一个...
标题中的“动态规划算法学习十例之五”表明这篇内容主要关注的是计算机科学中的动态规划算法,这是一种在解决复杂问题时非常有效的优化方法。动态规划通常用于处理具有重叠子问题和最优子结构的问题,通过将大问题...
在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...
在这个“动态规划算法学习十例之一”的主题中,我们将会探讨动态规划的基本概念和一个具体的实例,通过分析`Test.java`源码来深入理解。 首先,动态规划的核心思想是将一个大问题分解为相互重叠的小问题,并通过...
动态规划是一种重要的算法思想,广泛应用于解决复杂问题的优化,如最短路径、背包问题、最长公共子序列等。在本篇文章中,我们将探讨动态规划的精髓,并通过具体实例进行深入学习。博客链接提供了详细的解析,虽然...
在压缩包中的"近似串匹配问题"文件可能包含了这样的C语言实现,可以作为学习和理解近似串匹配动态规划算法的一个实例。 总结一下,近似串匹配的动态规划算法是一种高效的方法,通过Levenshtein距离或Hamming距离...
三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的主题。下面将对这三个方面进行详细的...
在课程设计过程中,学生还将学习如何分析动态规划算法的时间复杂度和空间复杂度。例如,大多数动态规划解决方案的时间复杂度为O(n*W),其中n是物品数量,W是背包容量,而空间复杂度通常是O(n*W)或者更优,取决于是否...
动态规划算法以其卓越的能力,成为应对这类问题的首选工具。它通过把复杂问题分解成更小、更易于管理的子问题,以递归的方式进行解决。这种方法不仅效率高,而且在很多情况下比其他算法(如贪婪算法或分治算法)更优...
在实际编程中,理解和掌握动态规划算法对于提高问题解决能力至关重要,因为它能够优雅地处理复杂度高且具有结构重叠的优化问题。在学习动态规划时,推荐阅读如《Introduction to Algorithms》等经典教材,它们深入浅...
标题中提到的是“算法参考资料国际大学生程序设计竞赛例题解3 图论·动态规划算法·综合题专集”。这份资料集中的标题揭示了内容的几个关键点,即它是一份专门为解决算法问题而编写的参考资料,特别针对国际大学生...
以斐波那契数列为例,F(n) = F(n-1) + F(n-2),我们可以创建一个二维数组dp[i][j]来存储F(i)的第j位数字,避免重复计算。对于给定的n,从F(0)和F(1)开始计算,直到得到F(n)。 总结,动态规划是一种强大的算法工具,...
动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...
在本课程“算法提高-动态规划(二)”中,我们将深入探讨动态规划的原理、应用及其优化技巧。 首先,理解动态规划的核心概念至关重要。动态规划的基本思想是将一个大问题分解为多个小问题,通过解决这些小问题来...
"基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf" 本文研究主要集中在基于岭回归机器学习算法的项目成本预测研究,以A风景园林规划研究院规划设计项目为例。该研究的目的...