动态规划

原创
2017/04/16 20:20
阅读数 40

背包问题具体例子:假设现有容量10kg的背包,另外有3个物品,分别为a1,a2,a3。物品a1重量为3kg,价值为4;物品a2重量为4kg,价值为5;物品a3重量为5kg,价值为6。将哪些物品放入背包可使得背包中的总价值最大?

首先想到的,一般是穷举法,一个一个地试,对于数目小的例子适用,如果容量增大,物品增多,这种方法就无用武之地了。

  其次,可以先把价值最大的物体放入,这已经是贪婪算法的雏形了。如果不添加某些特定条件,结果未必可行。

  最后,就是动态规划的思路了。先将原始问题一般化,欲求背包能够获得的总价值,即欲求前i个物体放入容量为m(kg)背包的最大价值c[i][m]——使用一个数组来存储最大价值,当m取10,i取3时,即原始问题了。而前i个物体放入容量为m(kg)的背包,又可以转化成前(i-1)个物体放入背包的问题。下面使用数学表达式描述它们两者之间的具体关系。

  表达式中各个符号的具体含义。

  w[i] :  第i个物体的重量;

  p[i] : 第i个物体的价值;

  c[i][m] : 前i个物体放入容量为m的背包的最大价值;

  c[i-1][m] : 前i-1个物体放入容量为m的背包的最大价值;

  c[i-1][m-w[i]] : 前i-1个物体放入容量为m-w[i]的背包的最大价值;

  由此可得:

      c[i][m]=max{c[i-1][m-w[i]]+pi , c[i-1][m]}(下图将给出更具体的解释)

  根据上式,对物体个数及背包重量进行递推,列出一个表格(见下表),表格来自(http://blog.csdn.net/fg2006/article/details/6766384?reload) ,当逐步推出表中每个值的大小,那个最大价值就求出来了。推导过程中,注意一点,最好逐行而非逐列开始推导,先从编号为1的那一行,推出所有c[1][m]的值,再推编号为2的那行c[2][m]的大小。这样便于理解。

  思路厘清后,开始编程序,Java代码如下所示:

复制代码

public class BackPack {
    public static void main(String[] args) {
        int m = 10;
        int n = 3;
        int w[] = {3, 4, 5};
        int p[] = {4, 5, 6};
        int c[][] = BackPack_Solution(m, n, w, p);
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <=m; j++) {
                System.out.print(c[i][j]+"\t");
                if(j==m){
                    System.out.println();
                }
            }
        }
        //printPack(c, w, m, n);

    }

 /**
     * @param m 表示背包的最大容量
     * @param n 表示商品个数
     * @param w 表示商品重量数组
     * @param p 表示商品价值数组
     */
    public static int[][] BackPack_Solution(int m, int n, int[] w, int[] p) {
        //c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值
        int c[][] = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++)
            c[i][0] = 0;
        for (int j = 0; j < m + 1; j++)
            c[0][j] = 0;

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                //当物品为i件重量为j时,如果第i件的重量(w[i-1])小于重量j时,c[i][j]为下列两种情况之一:
                //(1)物品i不放入背包中,所以c[i][j]为c[i-1][j]的值
                //(2)物品i放入背包中,则背包剩余重量为j-w[i-1],所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值
                if (w[i - 1] <= j) {
                    if (c[i - 1][j] < (c[i - 1][j - w[i - 1]] + p[i - 1]))
                        c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1];
                    else
                        c[i][j] = c[i - 1][j];
                } else
                    c[i][j] = c[i - 1][j];
            }
        }
        return c;
    }

复制代码

运行结果为:

复制代码

0    0    4    4    4    4    4    4    4    4    
0    0    4    5    5    5    9    9    9    9    
0    0    4    5    6    6    9    10    11    11    

Process finished with exit code 0

一、基本概念

    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

二、基本思想与策略

    基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

    由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

    与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。

 

 

三、适用的情况

能采用动态规划求解的问题的一般要具有3个性质:

    (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

    (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

   (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

 

四、求解的基本步骤

     动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。

    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

                      图1 动态规划决策过程示意图

    (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。

    (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

    (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

    (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

    一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。

实际应用中可以按以下几个简化的步骤进行设计:

    (1)分析最优解的性质,并刻画其结构特征。

    (2)递归的定义最优解。

    (3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值

    (4)根据计算最优值时得到的信息,构造问题的最优解

 

五、算法实现的说明

    动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。

     使用动态规划求解问题,最重要的就是确定动态规划三要素:

    (1)问题的阶段 (2)每个阶段的状态

    (3)从前一个阶段转化到后一个阶段之间的递推关系。

     递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。

    确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

          f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

 

 

六、动态规划算法基本框架

 

[cpp] view plain copy

 print?

  1. for(j=1; j<=m; j=j+1) // 第一个阶段  
  2.     xn[j] = 初始值;  
  3.    
  4.   for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段  
  5.     for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式  
  6.       xi[j]=j=max(或min){g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};  
  7.    
  8.  t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案  
  9.    
  10.  print(x1[j1]);  
  11.    
  12.  for(i=2; i<=n-1; i=i+1)  
  13.  {    
  14.       t = t-xi-1[ji];  
  15.    
  16.       for(j=1; j>=f(i); j=j+1)  
  17.          if(t=xi[ji])  
  18.               break;  
  19.  } 

这道最大m子段问题我是在课本《计算机算法分析与设计》上看到,课本也给出了相应的算法,也有解这题的算法的逻辑。但是,看完之后,我知道这样做可以解出正确答案,但是我如何能想到要这样做呢? 课本和网上的某些答案都讲得比较晦涩,有些关键的步骤不是一般人可以想得到的。不仅要知其然,还要知其所以然。否则以后我们遇到类似的问题还是不会解。

 

下面是我解这道题的思考过程。我按照自己的想法做,做到最后发现和课本的思想差不多,也有一点差别。如果对这道题有些不明白,可以仔细看看,相信看完之后你会豁然开朗。

 

 

问题: 给定n个整数(可能为负数)组成的序列 以及一个正整数m,要求确定序列的m个不相交子段,使这m个子段的总和达到最大。

 

0 首先举个例子方便理解题目  如果 = {1,-2,3,4,-5,-6,7,8,-9}  m=2  明显所求两个子段为{3,4}{7,8}  最大m子段和为26。

 

1 先想如何求得最大子段和。

 

1.1最容易想到的方法是穷举法。列出所有的子段组合,求出每个组合的子段和,所有组合中最大者即为所求。

 

仔细分析后发现:计算量巨大且难以实现。果断放弃。

 

1.2 分析:用数组a[1…n]来表示一个序列,用二维数组SUM[n][m]表示由数组a的前n个数字组成的子序列的最大m子段。(可知  n>=m)

 

SUM[n][m]即为所求.

 

分析最后一个数字a[n]所有可能的情况

1)       a[n] 不属于构成最大m子段和的一部分, SUM [n][m] = SUM [n-1][m]

 

2)       a[n] 属于构成最大m子段和的一部分, 且a[n]单独作为一个子段。

 

此时SUM[n][m] = SUM[n-1][m-1]+a[n];

 

3)       a[n] 属于构成最大m子段和的一部分, 且a[n]作为最后一个子段的一部分。

 

此时比较复杂, a[n]只是作为最后一个子段的一部分, 所以a[n-1]也一定在最后一个子段之中,否则a[n]便是一个单独的子段,前后矛盾.

 

所以SUM[n][m] = (包含a[n-1]的由前n-1个数字组成的子序列的最大m子段和) + a[n]

若用 b[n][m] 表示包含a[n]的、由前n个数字组成的子序列 的最大m子段和。

 

则 SUM[n][m] = b[n-1][m] + a[n]

 

1.3 我们仔细观察第三种情况里面定义的b[n][m]: 包含a[n]的、由前n个数字组成的子序列   的最大m子段和。

 

         假设a[k] (k∈[m,n])是 原问题的解中的最后一个子段的最后一个元素, 则b[k][m]即为原问题的最大子段和。(若不明白再多看b的定义几次~)

         所以原问题所求的最大子段和SUM[n][m]为 

 

1.4 现在就好办了, 分析b[n][m]的值如何计算。

回顾我们刚刚对a[n]的分析的三种情况中的后面两种

1)       a[n]单独作为一个子段,

则 b [n][m] = SUM[n-1][m-1] + a[n]

(而SUM[n-1][m-1]=  )
 

2)       a[n]作为末尾子段的一部分

则 b[n][m] = b[n-1][m]+a[n]
 

分别计算情况1) 和情况2) 下的b[n][m], 比较, 取较大者.

a)         特殊情况,
  若m=n 则a[n]为单独子段 按情况1)计算
  若n=1 则SUM[n][m] = a[n] 

 

1.5 到这里很明显可以看出这是一个动态规划的问题,还不太懂动态规划也没关系,你只要记得,要计算b[i][j], 需要有:SUM[i-1][j-1]、b[i-1][j] 。

 

而 SUM[i-1][j-1]由数组b算出。需要先算出   b[k][j-1]  (j-1<=k <=i-1 )。参见前面SUM的推导.  

 

所以我需要先知道 b[k][j-1] (j-1<=k <=i-1 ) 以及 b[i-1][j]

 

所以,数组b 如何填写?不明白可以画个表看看

 

 

  

 

比如上表:在求SUM[8][4]时,我们需要先求的为图中黄色区域.

 

黑色部分不可求(无意义), 白色部分在求解的时候不需要用到.

 

可以看出 我们只需要求 当  1<=j<=m  且 j<=i<=n-m+j  部分的b[i][j]就可以得出解.(此处我用画图 有谁可以有更方便的方法来理解欢迎讨论)

 

至此 我们大概知道此算法如何填表了,以下为框架.

for(int j=1; j<=m ; j ++)

         for(int i= j ;i <= n-m + i ; j++)    

 

 

1.6 开始写算法(我用java 实现)

 

复制代码

1 package com.cpc.dp;
 2 
 3 public class NMSum {
 4 
 5     public static void Sum(int[] a  ,int m ) {
 6         
 7         int n = a.length;        // n为数组中的个数
 8         int[][] b = new int[n+1][m+1];        
 9         int[][] SUM = new int[n+1][m+1];
10         
11         for(int p=0;p<=n;p++)    {   // 一个子段获数字都不取时   // 
12             b[p][0] = 0;
13             SUM[p][0] = 0;
14         }
15 //        for(int p=0;p<=m;p++)    {   // 当p > 0 时 并无意义, 此部分不会被用到,注释掉
16 //        b[0][p] = 0;
17 //        SUM[0][p] = 0;
18 //    }
19         for(int j=1;j<=m;j++){
20             for (int i = j;i<=n-m+j;i++){
21                 
22                 // n=1 m=1  此时最大1子段为 a[0]  java 数组为从0开始的 需要注意 后面所有的第i个数为a[i-1];
23                 if(i==1){
24                     b[i][j] = a[i-1];    
25                     SUM[i][j] = a[i-1];
26                 }else 
27                 {
28                     //先假设 第i个数作为最后一个子段的一部分
29                     b[i][j] = b[i-1][j] + a[i-1];
30 
31                     // 若第i个数作为单独子段时 b[i][j]更大  则把a[i-1] 作为单独子段
32                     // 考虑特殊情况  若第一个数字为负数    b[1][1]为负数  在求b[2][1] SUM[1][0]=0>b[1][1] 则舍去第一个数字  此处合理
33                     if(SUM[i-1][j-1]+a[i-1] > b[i][j]) b[i][j] = SUM[i-1][j-1] + a[i-1];
34 
35                     //填写SUM[i][j]供以后使用
36                     if(j<i){ // i 比j 大时
37                         if(b[i][j]>SUM[i-1][j]){  //  用b[i][j] 与之前求的比较
40                             SUM[i][j] = b[i][j];
41                         }else {
42                             SUM[i][j] = SUM[i-1][j];
43                         }
44                     }else   // i = j 
45                     {
46                         SUM[i][j] = SUM[i-1][j-1] + a[i-1];
47                     }
48                 }
49             }//end for
50         }// end for
51         System.out.println(SUM[n][m]);        // 输出结果
52     }// end of method
53 
54     public static void main(String[] args) {
55         int[] a = new int[]{1,-2,3,4,-5,-6,7,18,-9};
56         Sum(a, 3);
57     }
58 }

复制代码

output : 33

测试通过

 

/************** 4.22 更新***************************/

 

2 算法的优化

2.1 分析 算法的空间复杂度 为O(mn).我们观察一下,在计算b[i][j]时 我们用到b[i-1][j] 和 SUM[i-1][j-1],也就是说,每次运算的时候 我们只需要用到数组b的这一行以及数组SUM的上一行.

我们观察一下算法的框架

 

for(int j=1; j<=m ; j ++)       

         for(int i= j ;i <= n-m + i ; j++)    

    // 计算b[i][j]   需要  SUM[i-1][j-1]  和 b[i-1][j]    

    // 计算SUM[i][j]   需要 SUM[i-1][j]  b[i][j] SUM[i-1][j-1]

 

假设在 j=m 时(即最外面的for循环计算到最后一轮时)

要计算b[*][j]     *∈[m,n]

我只需要知道 SUM[*-1][j-1]       b[*-1][j]       (即需要上一轮计算的数组SUM以及这一轮计算的数组b)

而之前所求的数组SUM和数组b其他部分的信息已经无效,

我们只关心最后一轮计算的结果,而最后一轮计算需要倒数第二轮计算的结果.

倒数第二轮计算需要再倒数第三结果.以此循环

 

因此我们可以考虑重复利用空间,

在一个位置所存储的信息已经无效的时候,可以覆盖这个位置,让它存储新的信息.

 

举个例子:  老师在黑板上推导某一个公式的时候, 黑板的面积有限,而有时候推导的过程十分长,很快黑板不够用了,这个老师通常会擦掉前面推导的过程,留下推导下一步要用的一部分,在擦掉的地方继续写.

 

 

但是如何安全地覆盖前面失效的内容而不会导致覆盖掉仍然需要使用的内容呢?

分析后可以得知一下约束:

1) 求b[i][j] 需要用到SUM[i-1][j-1]  所以SUM[i-1][j-1]必须在b[i][j]的值求完后才可以被覆盖

2) 求b[i][j] 需要用到 b[i-1][j]  (j 相等)

3) 求SUM[i][j] 需要用到 SUM[i-1][j]    (j 相等)

4) 求SUM[i][j] 需要用到 b[i][j]   (j 相等)

5) 求SUM[i][j] 需要用到SUM[i-1][j-1]  (i的位置错开)

 

对于最外面的for循环

我们只关心最后一轮(也就是第(j=m)轮)的结果,所以考虑把两个二维数组变成一维数组b[1...n]  、SUM[1..n]

假设在第j轮计算后:

b[i] 表示的意义与原来的 b[i][j]相同   ( 也就是原来的b[i][j]会覆盖b[i][j-1] )

SUM[i]  表示什么呢  

我们观察约束1)知道,在第j 轮计算 b[i] (即原来的b[i][j])时,仍然会用到原来SUM[i-1][j-1],

也就是说 , 在计算b[i]时,SUM[i-1] 需要存储的是原来的SUM[i-1][j-1]

 

对于里面的for 循环

由于计算 b[i]需要SUM[i-1]

所以在计算完b[i]  后才计算新的SUM[i-1]  

即在b[i]计算完后,可以覆盖掉SUM[i-1]  使之表示原来的SUM[i-1][j]

也就是说, 在第j轮计算完毕后, SUM[i] 表示的意义与原来的SUM[i][j]相同

 

 

2.2 分析得差不多了, 废话少说,开始优化代码

复制代码

1 package com.cpc.dp;
 2 
 3 public class NMSUM2 {
 4 
 5     public static void Sum(int[] a  ,int m ) {
 6 
 7         int n = a.length;        // n为数组中的个数
 8         int[] b = new int[n+1];        
 9         int[] SUM = new int[n+1];
10 
11         b[0] = 0;// 一个子段获或者数字都不取时 ,也可以不设置,因为 java默认int数组中元素的初始值为0
12         SUM[1] = a[0];
13 
14         for(int j=1;j<=m;j++){
15             b[j] = b[j-1] + a[j-1];            // i=j 时
16             SUM[j-1] = -1;          // 第j 轮  SUM[j-1]表示原来的 SUM[j-1][j] 无意义 设置为-1 
17             int temp = b[j];
18             for (int i = j+1;i<=n-m+j;i++){
19 
20                 //先假设 第i个数作为最后一个子段的一部分
21                 b[i] = b[i-1] + a[i-1];
22                 // 若第i个数作为单独子段时 b[i][j]更大  则把a[i-1] 作为单独子段
23                 if(SUM[i-1]+a[i-1] > b[i]) b[i] = SUM[i-1] + a[i-1];
24                 
25                 //下面原来计算的是原来的SUM[i][j] ,但是现在要修改的应该是原来的SUM[i][j-1] ,如何把SUM[i][j]保存 下来?
26                 // 可以在循环外面定义一个变量temp来暂存 等下一次循环再写入
27                 SUM[i-1] = temp;  
28                 if(b[i]>temp){
29                     temp = b[i];    //temp 记录SUM[i][j] 
30                 }
31             }//end for
32             SUM[j+n-m] = temp;
33         }// end for
34         System.out.println(SUM[n]);        // 输出结果
35     }// end of method
36 
37     public static void main(String[] args) {
38         int[] a = new int[]{1,-2,3,4,-5,-6,7,18,-9};
39         Sum(a, 1);
40     }
41 }

复制代码

 

 output: 25

算法的空间复杂度变为o(n)~  优化完毕!

 

 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

二、基本思想与策略

    基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

    由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

    与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。

以上都过于理论,还是看看常见的动态规划问题吧!!!

三、常见动态规划问题

   1、找零钱问题

   有数组penny,penny中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim(小于等于1000)代表要找的钱数,求换钱有多少种方法。
给定数组penny及它的大小(小于等于50),同时给定一个整数aim,请返回有多少种方法可以凑成aim。
测试样例:
[1,2,4],3,3
返回:2

解析:设dp[n][m]为使用前n中货币凑成的m的种数,那么就会有两种情况:

             使用第n种货币:dp[n-1][m]+dp[n-1][m-peney[n]]

              不用第n种货币:dp[n-1][m],为什么不使用第n种货币呢,因为penney[n]>m。

        这样就可以求出当m>=penney[n]时 dp[n][m] = dp[n-1][m]+dp[n-1][m-peney[n]],否则,dp[n][m] = dp[n-1][m]

代码如下:

[java] view plain copy

  1. <span style="font-size:18px;">import java.util.*;  
  2.   
  3. public class Exchange {  
  4.     public int countWays(int[] penny, int n, int aim) {  
  5.         // write code here  
  6.         if(n==0||penny==null||aim<0){  
  7.          return 0;     
  8.         }  
  9.         int[][] pd = new int[n][aim+1];  
  10.         for(int i=0;i<n;i++){  
  11.          pd[i][0] = 1;     
  12.         }  
  13.         for(int i=1;penny[0]*i<=aim;i++){  
  14.          pd[0][penny[0]*i] = 1;     
  15.         }  
  16.         for(int i=1;i<n;i++){  
  17.             for(int j=0;j<=aim;j++){  
  18.                 if(j>=penny[i]){  
  19.                     pd[i][j] = pd[i-1][j]+pd[i][j-penny[i]];  
  20.                 }else{  
  21.                     pd[i][j] = pd[i-1][j];  
  22.                 }  
  23.             }  
  24.         }  
  25.         return pd[n-1][aim];  
  26.     }  
  27. }</span>  


2、走方格问题

  有一个矩阵map,它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径中最小的路径和。
给定一个矩阵map及它的行数n和列数m,请返回最小路径和。保证行列数均小于等于100.
测试样例:
[[1,2,3],[1,1,1]],2,3
返回:4

解析:设dp[n][m]为走到n*m位置的路径长度,那么显而易见dp[n][m] = min(dp[n-1][m],dp[n][m-1]);

 

代码如下:

[java] view plain copy

  1. <span style="font-size:18px;">import java.util.*;  
  2.   
  3. public class MinimumPath {  
  4.     public int getMin(int[][] map, int n, int m) {  
  5.         // write code here  
  6.        int[][] dp = new int[n][m];  
  7.         for(int i=0;i<n;i++){  
  8.             for(int j=0;j<=i;j++){  
  9.              dp[i][0]+=map[j][0];      
  10.             }  
  11.         }  
  12.         for(int i=0;i<m;i++){  
  13.             for(int j=0;j<=i;j++){  
  14.              dp[0][i]+=map[0][j];      
  15.             }  
  16.         }  
  17.         for(int i=1;i<n;i++){  
  18.             for(int j=1;j<m;j++){  
  19.              dp[i][j] = min(dp[i][j-1]+map[i][j],dp[i-1][j]+map[i][j]);     
  20.             }  
  21.         }  
  22.         return dp[n-1][m-1];  
  23.     }  
  24.     public int min(int a,int b){  
  25.         if(a>b){  
  26.          return b;     
  27.         }else{  
  28.          return a;     
  29.         }  
  30.     }  
  31. }</span>  


3、走台阶问题

有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。为了防止溢出,请将结果Mod 1000000007
给定一个正整数int n,请返回一个数,代表上楼的方式数。保证n小于等于100000。
测试样例:
1
返回:1

解析:这是一个非常经典的为题,设f(n)为上n级台阶的方法,要上到n级台阶的最后一步有两种方式:从n-1级台阶走一步;从n-1级台阶走两步,于是就有了这个公式f(n) = f(n-1)+f(n-2);

代码如下:

[java] view plain copy

  1. <span style="font-size:18px;">import java.util.*;  
  2.   
  3. public class GoUpstairs {  
  4.     public int countWays(int n) {  
  5.         // write code here  
  6.         if(n<=2)  
  7.             return n;  
  8.         int f = 1%1000000007;  
  9.         int s = 2%1000000007;  
  10.         int t = 0;  
  11.         for(int i=3;i<=n;i++){  
  12.          t = (f+s)%1000000007;  
  13.          f = s;  
  14.          s = t;  
  15.         }  
  16.        return t;   
  17.     }  
  18. }</span>  


4、最长公共序列数

给定两个字符串A和B,返回两个字符串的最长公共子序列的长度。例如,A="1A2C3D4B56”,B="B1D23CA45B6A”,”123456"或者"12C4B6"都是最长公共子序列。
给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。
测试样例:
"1A2C3D4B56",10,"B1D23CA45B6A",12
返回:6

解析:设dp[n][m] ,为A的前n个字符与B的前m个字符的公共序列长度,则当A[n]==B[m]的时候,dp[i][j] = max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]),否则,dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

代码如下:

[java] view plain copy

  1. <span style="font-size:18px;">import java.util.*;  
  2.   
  3. public class LCS {  
  4.     public int findLCS(String A, int n, String B, int m) {  
  5.         // write code here  
  6.         int[][] dp = new int[n][m];  
  7.         char[] a = A.toCharArray();  
  8.         char[] b = B.toCharArray();  
  9.        for(int i=0;i<n;i++){  
  10.            if(a[i]==b[0]){  
  11.                dp[i][0] = 1;  
  12.                for(int j=i+1;j<n;j++){  
  13.                    dp[j][0] = 1;  
  14.                }  
  15.                break;  
  16.            }  
  17.              
  18.        }  
  19.          for(int i=0;i<m;i++){  
  20.            if(a[0]==b[i]){  
  21.                dp[0][i] = 1;  
  22.                for(int j=i+1;j<m;j++){  
  23.                    dp[0][j] = 1;  
  24.                }  
  25.                break;  
  26.            }  
  27.              
  28.        }  
  29.        for(int i=1;i<n;i++){  
  30.            for(int j=1;j<m;j++){  
  31.                if(a[i]==b[j]){  
  32.                   dp[i][j] = max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]);  
  33.                }else{  
  34.                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);  
  35.                }  
  36.                      
  37.            }  
  38.        }   
  39.           
  40.         return dp[n-1][m-1];  
  41.     }  
  42.     public int max(int a,int b,int c){  
  43.         int max = a;  
  44.         if(b>max)  
  45.             max=b;  
  46.         if(c>max)  
  47.             max = c;  
  48.         return max;  
  49.     }  
  50. }

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部