动态规划

坐标型动态规划

题目

Unique Paths II 不同的路径之二

  • 给定m行n列的网格,有一个机器人从左上角(0,0)出发,每一步可以向下或者向右走一步
  • 网格中有些地方有障碍,机器人不能通过障碍格
  • 问有多少种不同的方式走到右下角

Unique Paths II

题目分析

  • 最后一步一定是从左边(i,j-1)或上边(i-1,j)过来
  • 状态fi标识从左上角有多少种方式走到格子(i,j)
  • 坐标型动态规划:数组下标i即坐标(i,j)

    f[i][j] = f[i-1][j] + f[i][j-1]

初始条件和边界情况

  • 如果左上角(0,0)格或者右下角(m-1,n-1)格有障碍,直接输出0
  • 如果(i,j)格有障碍,fi=0,表示机器人不能到达此格(0种方式)
  • 初始条件:f[0][0] =1 转移方程

题解

int uniquePathsWithObstacles(vector<vector<int>>A) {
    int m = A.size();   //得到A的行数
    if (m == 0)
        return 0;
    int n = A[0].size();    //得到A的列数
    if (n == 0)
        return 0;
    vector<vector<int>>f;    //开一个m行n列的数组
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (A[0][0] == 1)     //如果是障碍格,一票否决
                f[i][j] = 0;
            else {
                if (i == 0 && j == 0)  //左上角
                    f[i][j] = 1;
                else {        //加上左边和上边,但要先判断是不是0
                    f[i][j] = 0;
                    if (i - 1 >= 0) {    //如果有前面一行
                        f[i][j] += f[i - 1][j];
                    }
                    if (j - 1 >= 0) {        //如果有前面一列
                        f[i][j] += f[i][j];
                    }
                }
            }
        }
    }
    return f[m - 1][n - 1];
}

序列型动态规划

题目

Paint House 粉刷房子

  • 有一排N栋房子,每栋房子要漆成3种颜色中的一种:红、蓝、绿
  • 任何两栋相邻的房子不能漆成相同的颜色
  • 第i栋房子染成红色、蓝色、绿色的花费分别是cost[i][0],cost[i][1],cost[i][2]
  • 问最少需要花多少钱油漆这些房子

样例:

输入:

  • N=3
  • Cost = [[14,2,11],[11,14,5],[14,3,10]]

输出:

  • 10(第0栋房子蓝色,第1栋房子绿色,第2栋房子蓝色,2+5+3=10)

分析

确定状态

  • 最优策略是花费最小的策略
  • 最后一步:最优策略中房子N-1一定染成了红、蓝、绿中的一种
  • 但是相邻两栋房子不能漆成一种颜色
  • 所以如果最优策略中房子N-1是蓝色,房子N-2只能是红色或绿色

    • 所以如果最优策略中房子N-1是绿色,房子N-2只能是红色或蓝色
    • 所以如果最优策略中房子N-1是红色,房子N-2只能是蓝色或绿色
添加新评论