【数据结构算法】动态规划之【单序列问题】

目录

1.序言：了解动态规划

2.最小花费爬楼梯：

分析问题：

确定状态转移方程：

 代码实现：

3.最大子数组和

 分析问题：

状态转移方程：

代码实现：

4.打家劫舍

状态转移方程： 

代码实现：

改进：

5. 粉刷房子

问题分析：

状态转移方程：

代码实现：

---

1.序言：了解动态规划

浅浅的谈一谈我对动态规划的认识：

动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。 动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。 使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

找出描述的大问题的解和小问题之间的解递归关系或者迭代关系的状态转移方程是利用动态规划解决问题的关键；

接下来 我们将会用一个个列题带大家来熟悉一下动态规划中的单序列问题；

2.最小花费爬楼梯：

分析问题：

爬楼梯 一次只能怕=爬一层或者两层，每一步都两个选择；也许看起来很像可以用回溯法来解，但是这个问题不是来求有多少种方法来去爬到楼梯顶；这是一个求有最小的花费问题(最优解问题)，所以咱们这里用动态规划来解题；

确定状态转移方程：

既然是求最小成本，那么每一步的走法就可以分解成两个子问题，每一层可以选择爬一阶或者两阶楼梯，设 f [ i ] 为第 i 阶向上爬的最小成本，f [ i ]  如何取最小？这和 f [ i - 1 ] , f [ i - 2 ] 的值有关，就是取这两个值的最小值；即状态转移方程为：f [ i ] = min( f [ i - 1] +  cost [ i  - 1] , f [ i - 2 ] +  cost [ i  - 2] ); 

 代码实现：

int min(int a,int b)
{
    return a>b?b:a;
}
int minCostClimbingStairs(int* cost, int costSize){
    int i = 0;
    int f[10000] = {0,0};
    for(i = 2;i<=costSize;i++)
    {
        f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);
    }
    return f[costSize];
}

3.最大子数组和

 分析问题：

这一题和上一节当中讲到的【寂寞如雪】这题很像，基本是就是相同的问题；我们要求最大的子数组和，同样的我们要一步一步的分解，以第 i 个整数结尾的子树组分为两种情况 1.和第 i - 1 个整数结尾的子数组相连；2.单独以第 i 个整数作为子数组；

状态转移方程：

每一步都两个选择 以前一个是 i - 1的子数组 或者 以 单个  i  结尾的子数组，选好当下的每一步才能解出此题；设 f [ i ] 为最大子数组和，状态转移方程为 ： f [ i ] = max( f [ i - 1]  + nums[ i ] ,  nums[ i ] ) ; 举个简单的例子 nums = { -2 , 1} ; f [ 0 ] = { - 2 } ；f [ 1 ] = max( f [ 0 ] + nums[ 1 ] , nums[ 1 ] ) = { 1 };

代码实现：

int maxSubArray(int* nums, int numsSize) {
    int f[2] = { 0 };
    int i = 0;
    f[0] = nums[0];
    int maxvalue = nums[0];
    for (i = 1; i < numsSize; i++)
    {
        f[i % 2] = max(f[(i - 1) % 2] + nums[i], nums[i]);
        maxvalue = max(max(f[0], f[1]), maxvalue);
    }
    return maxvalue;
}

4.打家劫舍

题目都是类似；分析的情况一笔带过：

状态转移方程： 

题目的意思是不能偷相邻俩家的房子，不然会被发现，求偷盗的最大金额；设 f [ i ] 为小偷从 0 开始偷 到 i 的最大金额数；在标号为 i 的房子面前，小偷可以选择偷或者不偷，偷的话 i - 1不能偷，此时得到的金额为 f [ i - 2 ] + nums [ i ]；如果不偷，此时的金额为 f [ i - 1 ];由此可以得出状态转移方程：  f [ i ] = max ( f [ i - 1 ] , f [ i - 2 ] + nums [ i ] );

代码实现：

int max(int x,int y){
    return x>y?x:y;
}
 
int rob(int* nums, int numsSize){
    int i = 0;
    int f[1000];
    if(numsSize == 2)
        return max(nums[0],nums[1]);
    if(numsSize == 1)
        return nums[0];
    f[0] = nums[0];
    f[1] = max(nums[0],nums[1]);
    for(i = 2;i<numsSize;i++)
    {
        f[i] = max(f[i-1],f[i-2] + nums[i]);
    }
    return f[numsSize-1];
}

改进：

因为 在这个状态转移方程里面 有效的数位只有两个；所以我们可以只给数组的长度为 2 来处理

像这样：

int rob(int* nums, int numsSize){
//f[i] = max(f[i-1],f[i-2] + nums[i]);
 
    int i = 0;
    int f[2] = {0};
    if(numsSize == 2)
        return max(nums[0],nums[1]);
    if(numsSize == 1)
        return nums[0];
    f[0] = nums[0];
    f[1] = max(nums[0],nums[1]);
    for(i = 2;i<numsSize;i++)
    {
        f[i%2] = max(f[(i-1) % 2],f[(i-2)%2] + nums[i]);
    }
    //return max(f[0],f[1]);
    return f[(numsSize - 1) % 2];
}

5. 粉刷房子

问题分析：

这类问题算的上是动态规划类的进阶题了；一排 n 个房子，每个房子可以刷三种颜色；但是相邻的房子不能刷同样的颜色；这就意为着每一个步骤都有很多不同的选择，求最优解的问题，我们用动态规划来解；

状态转移方程：

要刷 n 个房子，而我们每一步最多只能考虑一个房子的选择；大问题化小问题 计算标号为 i 的房子的成本 那么 假设 粉刷标号为 i 的房子为红色的成本为 r ( i )  应该等于 第 i - 1 个 房子 粉刷 绿色 或蓝色的最小值 加上 第 i 个房子刷成红色的成本，写成动态转移方程：

r ( i ) = min ( g( i - 1) ,b ( i - 1) ) + cost [ i ] [ 0 ] ; 

b ( i ) = min ( r( i - 1) ,g ( i - 1) ) + cost [ i ] [ 1 ] ;   

g ( i ) = min ( r( i - 1) ,b ( i - 1) ) + cost [ i ] [ 2 ] ; 

代码实现：

int min(int x,int y)
{
    return x > y ? y : x; 
}
 
int minCost(int** costs, int costsSize, int* costsColSize){
// 动态规划：
// 1.设计状态 2.写出状态转移方程 3.设定初始状态 4.执行状态转移
// 5.返回最终解;
    if(costsSize == 0)
    return 0;
    else
    {
        int r[2] = {0};
        int g[2] = {0};
        int b[2] = {0};
        r[0] = costs[0][0];
        b[0] = costs[0][1];
        g[0] = costs[0][2];
 
        int i = 0;
        for(i = 1;i<costsSize;i++)
        {
            r[i % 2] = min(g[(i-1) % 2],b[(i-1) % 2]) + costs[i][0];
            b[i % 2] = min(g[(i-1) % 2],r[(i-1) % 2]) + costs[i][1];
            g[i % 2] = min(r[(i-1) % 2],b[(i-1) % 2]) + costs[i][2];
        }
        i--;
        int D = min(r[i % 2],g[i % 2]);
        return min( D, b[i % 2] );
    }
 
}