动态规划题目特点

 

 

 

D1 动态规划概述

动态规划的组成状态

1. 确定状态
   1. 解开动态规划需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么
      1. 化成子问题（最少的硬币拼出更小的面值27-ak）
      2. 最后一步（最优策略中使用的最后一枚硬币ak）
      3. 子问题变成最少用多少硬币拼出27-ak
2. 确定转移方程,那么ak等于多少呢？
   • f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}
   • f[27]=min{f[27-2]+1,f[27-5]+1,f[27-7]+1}
3. 初始条件和边界情况
   • 边界小于0怎么办？什么时候停下来？
   • f[0]=0，如果不能拼出Y，f[Y]=正无穷
4. 计算顺序
   • 一般从小到大（避免重复计算）

最值型-硬币

Problem

你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多，买一本书需要27元，如何用最少的硬币组合正好付清，不需要对方找钱

//	A:{2,5,7}  M:27
public int coinChange(int[] A,int M){
    //0...n-1 :[n]
    //0...n   :[n+1]
    int[]  f = new int[M+1];//这里要用到27，故开辟M+1
    int n = A.length;//硬币的个数
    f[0]=0;
    int i,j;
    //f[1],f[2],...,f[27]
    for(i=1;i<=M;i++){
        f[i]=Integer.MAX_VALUE;
        //f[i]=min{f[i-A[0]]+1,...,f[i-A[n-1]]+1}
        for(j=0;j<n;j++){
            //如果数组不越界，且不超出最大值
            if(i>A[j] && f[i-A[j]]!=Integer.MAX_VALUE){
                f[i]=Math.min{f[i-A[j]]+1,f[i]};
            }  
        }
    }
    if(f[M]==Integer.MAX_VALUE){
        f[M]=-1;
    }
    return f[M];
}

计数型-机器人

Problem

给定m行n列的网格，有一个机器人从左上角(0,0)出发，每一步可以向下或者向右走一步，问有多少种不同的方式走到右下角(m-1,n-1)

public int uniquePaths(int m,int n){
    int[][] f = new int[m][n];
    int i,j;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            if(i==0||j==0)
                f[i][j]=1;
            else
                f[i][j] = f[i-1][j] + f[i][j-1];
        }
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

存在型-青蛙跳石子

Problem

有n块石头分别在x轴的0，1，。。。，n-1位置.一只青蛙在石头0，像跳到石头n-1。如果青蛙在第i块石头上，他最多可以向右跳距离ai。问青蛙能否跳到石头n-1

Example

Input:a=[2,3,1,1,4]
Output:True
Input:a=[3,2,1,0,4]
Output:False

• 1
• 2
• 3
• 4

public boolean canJump(int[] A){
    int n = A.length;
    boolean[] f = new boolean[n];
    f[0]=true;//initialization
    for(int j=1;j<n;j++){
        f[j] = false;
        //previous stone i
        //last jump is from i to j
        for(int i=0;i<j;i++){
            if(f[i]&&i+A[i]>=j){
                f[j] = true;
                break;
            }
        }
    }
    return f[n-1];
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

机器人2（坐标型）

Problem

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

public int uniquePathsWithObstacles(int[][] A){
    int m = A.length;
    if(m==0){
        return 0;
    }
    int n = A[0].length;
    if(n==0){
        return 0;
    }
    int[][] f = new int[m][n];
    int i,j;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            //Obstacles
            if(A[i][j]==1){
                f[i][j]=0;
                continue;
            }
            //top-left
            if(i==0&&j==0){
                f[i][j]=1;
                continue;
            }
            f[i][j]=0;
            //若不为第一行
            if(i>0){
                f[i][j]+=f[i-1][j];
            }
            //若不为第一列
            if(j>0){
                f[i][j]+=f[i][j-1];
            }
            //若两个条件都成立，则为f[i][j]=f[i-1][j]+f[i][j-1];
        }
    }
    return f[m-1][n-1];
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37

leetcode256-粉刷房子（序列型）

题目描述

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2]表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。

分析

确定状态：

• 不知道房子N-2是什么颜色，就把它记录下来
• 分别记录油漆前N-1栋房子并且房子N-2是红色、蓝色、绿色的最小花费

**子问题：**设油漆前i栋房子并且房子i-1是红色、蓝色、绿色的最小花费分别为f[i][0]、f[i][1]、f[i][2]

转移方程：

• f[i][0]=min{f[i-1][1]+cost[i-1][0],f[i-1][2]+cost[i-1][0]}
• f[i][1]=min{f[i-1][0]+cost[i-1][1],f[i-1][2]+cost[i-1][1]}
• f[i][2]=min{f[i-1][0]+cost[i-1][2],f[i-1][1]+cost[i-1][2]}

public int minCost(int[][] c){
    int n = c.length;
    if(n==0){
        return 0;
    }
    //sequence type DP
    int[][] f = new int[n+1][3];
    f[0][0]+f[0][1]+f[0][2]=0;
    int i,j,k;
    for(i=1;i<=n;i++){
        //color of house i-1: j
        for(j=0;j<3;j++){
            f[i][j]=Integer.MAX_VALUE;
            //color of house i-2: k
            for(k=0;k<3;k++){
                if(j!=k){
                    f[i][j]=Math.min(f[i][j],f[i-1][k]+c[i-1][j]);
                }
            }
        }
        return Math.min(f[n][0],Math.min(f[n][1],f[n][2]));
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23

Decode Ways

题意：

有一段由A-Z组成的字母串信息被加密成数字串，加密方式为：A->1，B->2，… ,Z->26，给定加密后的数字串S[0…N-1]，问有多少种方式解密成字母串

样例

Input
12
Output
2（AB or L）

• 1
• 2
• 3
• 4

分析

状态：设数字串S前i个数字解密成字母串有f[i]种方式

转移方程：设数字串S前i个数字解密成字母串有f[i]种方式

​ f[i] = f[i-1]|S[i-1]对应一个字母 + f[i-2]|S[i-2]S[i-1]对应一个字母

• 数字串S前i个数字解密成字母串的方式数
• 数字串S前i-1个数字解密成字母串的方式数
• 数字串S前i-2个数字解密成字母串的方式数

public int numDecodings(String ss){
    char[] s = ss.toCharArray();
    int n = s.length;
    if(n==0)return 0;
    int[] f = new int[n+1];
    f[0]=1;
    int i,j;
    for(i=1;i<=n;i++){
        f[i]=0;
        if(s[i-1]>='1'&&s[i-1]<='9'){
            f[i]+=f[i-1];
        }
        //check whether i>1
        if(i>1){
            //s[i-1][i-1]
            j=10*(s[i-2]-'0')+(s[i-1]-'0');
			if( j>=10 && j<=26){
				f[i] += f[i-2];
			}
        }
    }
    return f[n];
}