对动态规划的浅薄理解

动态规划

动态规划对于一个算法初学整来说并不好懂，但是通过做题和画图推理，是能够发现动态规划问题的共性的。

最大k乘积问题

问题分析

手推过程

算法实现

package com.dwx.passage3;

//十进制数最大k累积
public class demo3_1 {
    public int k; //表示子序列分隔的位置
    public int i;//表示数组开始的位置
    public int j;//表示数组结束的位置
    public int m;//表示执行几次划分
    public int[][] dp;//存储数据的数组
    public int[] l;//存放我们十进制数的整数数组

    public int getK() {
        return k;
    }

    public void setK(int k) {
        this.k = k;
    }

    public int getI() {
        return i;
    }

    public void setI(int i) {
        this.i = i;
    }

    public int getJ() {
        return j;
    }

    public void setJ(int j) {
        this.j = j;
    }

    public int[][] getDp() {
        return dp;
    }

    public void setDp(int[][] dp) {
        this.dp = dp;
    }

    public int[] getL() {
        return l;
    }

    public void setL(int[] l) {
        this.l = l;
    }

    public int getM() {
        return m;
    }

    public void setM(int m) {
        this.m = m;
    }

    //这个问题的动态规划方法
    public void demo(){
        //先对我们获得的数组进行初始化
        //一般第一列和第一行我们都跳过不进行初始化 为了方便理解将数字中的i与我们计算机中的第i列相对应
        int a,b,c,d;
        for (a = i;a <= j; a++){
            dp[a][1] = getNumber(i,a);
        }
        //对除了第一行以外的其他的元素进行操作

        //对第二列进行操作
        for (b=2;b<=m;b++){
            for (c = 2;c<=(j-i)+1;c++){
                int max = 0;
                for (k=c-1;k>=1;k--){
                    if (dp[k][b-1]*getNumber(k+1,c)>max)
                        max = dp[k][b-1]*getNumber(k+1,c);
                }
                dp[c][b] = max;
            }
        }

    }




    //先编写一个获取数值的方法
    int getNumber(int i,int j){
        int number = 0;
        int x = 1;
        for (int k = j;k>=i;k--){
            number = number + l[k]*x;
            x = x * 10;
        }
        return number;
    }
}

验证

import com.dwx.passage3.demo3_1;

public class demo3_1Test {
    public static void main(String[] args) {
        int i = 1;
        int j = 4;
        int m = 4;
        int dp[][] = new int[5][5];
        int[] l = new int[]{0,1,2,3,4};
        demo3_1 demo3_1 = new demo3_1();
        demo3_1.setDp(dp);
        demo3_1.setI(i);
        demo3_1.setJ(j);
        demo3_1.setL(l);
        demo3_1.setM(m);
        demo3_1.demo();
        int[][] dp1 = demo3_1.getDp();
        for (i=1;i<=j;i++){
            for (int x=1;x<=j;x++){
                System.out.print(dp1[i][x]+"\t");
            }
            System.out.println();
        }

    }
}

输出

1	0	0	0	
12	2	0	0	
123	36	6	0	
1234	492	144	24	

我们可以看到，我们的输出和我们手推的结果一样，因此这个算法程序是正确的。

总结

从上边的的几个案例我们可以看到，动态规划就是一个空间换时间的算法思路。动态规划求一个问题的最优解也是把整个问题的所有情况全部遍历了一边，但是比起一般的遍历，动态规划因为使用了dp矩阵，因此之前计算过的情况全部存放在dp矩阵里，减少了计算的次数，因此有人说动态规划是一种带记忆的遍历。

动态规划的解题思路是：

• 找到递推公式
• 确定dp矩阵的行向量和列向量的含义
• 自底而上一步步求解一步步动态规划
• 就得到了一个东西的所有情况

动态规划并没有一个固定的算法，不能和之前在数据结构中学习到的算法混为一谈。

在我看来动态规划只是一种思路，这种思路需要逻辑性。

最快学会学清除动态规划的方法就是，自己把一个动态规划题目的dp矩阵手推出来

就能理解程序的处理过程了。

Donate