2022-08-28

dp

第一次学习动态规划算法，上学期算法课没有选，现在开始补呜呜。

动态规划类问题，感觉写出状态转移方程是难点。这类题目一般要看出来怎么总结出什么是dp数组，转移的过程是什么。接下来通过leetcode上面一些经典的入门题目加深理解。

简单题：

斐波那契数(509) √
爬楼梯(70) √
使用最小花费爬楼梯(746) √
最大子数列和(53) √

入门：

打家劫舍(198) √
删除并获得点数(740) √
解码方法(91) √
最长递增子序列(300)
最长递增子序列个数(673)
买卖股票的最佳时机(122)

基础题

斐波那契数(leetcode第509题)

这个可以理解为就是介绍了一下什么是状态转移方程。其实斐波那契数列就是一个最最简单的迭代过程。实际上我觉得迭代法实际上就是动态规划(不知道这样想对不对)

int fib(int n){
    int num[3] = {0};
    num[0] = 0;
    num[1] = 1;
    int i = 0;
    for(i=2;i<=n;i++)
    {
        num[i%3] = num[(i-1)%3]+num[(i-2)%3];
    }
    return num[n%3];
}

爬楼梯(leetcode第746题)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

这里问的是方法的种类数。其实提示的也比较明显。假设我们用way[i]表示爬到第i层的方法总数，那么很容易得到

$way[i] = way[i-1] + way[i-2]$

仔细一看，这正是斐波那契数。这道题的状态转移方程正好是斐波那契数列，也算是对于斐波那契数列的一个回顾。一个小小的联想练习。

int climbStairs(int n){
    int way[10000] = {0};
    way[0] = 1;
    way[1] = 2;
    int i = 0;
    for(i=2;i<n;i++)
    {
        way[i] = way[i-1]+way[i-2];
    }
    return way[n-1];
}

使用最小花费爬楼梯(leetcode第746题)

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-cost-climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题的条件转移也是比较容易写出来的。观察下式，其中money[i]代表了走到第i层的花费，下面式子的意义也就是，第i层的花费其实就是从i-1层或者i-2层过来，分别加上对应的开销即可。

$money[i] = min(money[i-1]+cost[i-1],money[i-2]+cost[i-2])$

以下是代码。

int min(int a,int b)
{
    return a < b ? a : b;
}


int minCostClimbingStairs(int* cost, int costSize){
// money[i] = min(money[i-1]+cost[i-1],money[i-2]+cost[i-2])
    int money[1010] = {0};
    money[0] = 0;
    money[1] = 0;
    int i =0;
    for(i=2;i<=costSize;i++)
    {
        money[i] = min(money[i-1]+cost[i-1],money[i-2]+cost[i-2]);
    }
    return money[costSize];

}

最大子列和(leetcode第53题)

sol1: 在线求解法

这道题目很经典，也有很多解题方法。第一种是在线求解法，这种方法比较巧妙，依赖于观察(突然回想起来两年前我在预习数据结构的时候，好像也用这个方法做过这道题，时间过得好快啊)。主要是观察到一旦和小于0，就说明需要重置当前求和的结果为0，相当于是从当前位置开启一段新的数列。否则可以在当前的基础上继续加。

int max(int a,int b)
{
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize){
    int this_sum = 0;
    int max_sum = nums[0];
    int i =0;
    for(i=0;i<numsSize;i++)
    {
        this_sum += nums[i];
        if(this_sum>max_sum)
        {
            max_sum = this_sum;
        }
        if(this_sum<0)
        {
            this_sum = 0;
        }
    }
return max_sum;
}

sol2: 动态规划法

这种方法需要的内存比上面一种多很多。具体思想是，用dp[i]来表示计算到第i位时的最大子列和。注意这个子列并不一定是原先数列开头开始的，而是每一步都计算的是当前位置作为结束点时的最大和。

$dp[i] = max(dp[i-1]+nums[i], nums[i])$

也就是说，如果上面式子选择了nums[i]更大，那么就应当从nums[i]开始后面的子列。用一个示例模拟计算一下。

[-2,1,-3,4,-1,2,1,-5,4]

dp[0] = nums[0] = -2

dp[1] = max(dp[0]+nums[1],nums[1]) = max(-1,1) = 1表示如果完整的数列是[-2,1]，那么最大子列和是1

dp[2] = max(-2,-3) = -2，表示[-2,1,-3]最大子列和是-2

dp[3] = max(-2+4,4)=4，表示[-2,1,-3,4]的最大子列和是4

dp[4] = max(4-1,4) = 3,表示[-2,1,-3,4,-1]的最大子列和是3

dp[5] = max(3+2,2) = 5, 表示[-2,1,-3,4,-1,2]的最大子列和是5

dp[6] = max(5+1,1) = 6，表示[-2,1,-3,4,-1,2]的最大子列和是6

…..

代码如下所示

int max(int a,int b)
{
    return a > b ? a : b;
}



int maxSubArray(int* nums, int numsSize){
    int dp[100010];
    int i = 0;
    dp[0] = nums[0];
    int MAX = nums[0];
    for(i=1;i<numsSize;i++)
    {
        dp[i] = max(dp[i-1]+nums[i],nums[i]);
        if(dp[i]>MAX)
        {
            MAX = dp[i];
        }

    }
    return MAX;

}

入门题

解码方法(leetcode第91题)

一条包含字母 A-Z 的消息通过以下映射进行了编码：

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，”11106” 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。

题目数据保证答案肯定是一个 32位的整数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

~~这道题很奇怪，在远程泡会显示堆溢出，但是本地跑就没有问题。这题不能确定自己做的对不对。我的思路是用以下的状态变化。~~

~~$dp[cnt] = (dp[cnt - 1] + valid_one(s[i])) + (dp[cnt - 2] + valid_two(s[i - 1], s[i]))-dp[cnt-1];$~~

可能的编码总数。计算方法看dp[i-1]加上nums[i]，这是一种，也就是一个新的数字。第二种是考虑dp[i-2]+valid_two(s[i - 1], s[i]),也就是把最后两个数字作为一个整体。但是注意要两个结合起来会出现重复，重复的内容。

记录一下自己没认真审题造成的错误..。上面的算法是错的，因为我们不是计算解码的字符数量，而是计算能够成功解码的种类。这样的话假如下一个数字是’2’，并没有增加解码的种类数，结果将保持不变。

那么本题的状态转移可以写为

如果s[0] == ‘0’，无法解码
如果s[i] == ‘0’，并且s[i-1]=’1’或者s[i-1]=’2’，那么方案数量不变，dp[i] = dp[i-2]，否则方案数为0.
如果s[i] ！= ‘0’，如果s[i-1] == ‘1’，那么方案数为dp[i-1]+dp[i-2]
如果s[i] ！= ‘0’，如果s[i-1] == ‘2’，那么在s[i]<’6’的情况下，方案数为dp[i-1]+dp[i-2]
其余情况下均为s[i] = s[i-1]，即不变。

事实上，还有一些很刁钻的边界条件..导致我的代码对于数字特别小的时候特别简陋。一些刁钻的数字比如说”301”,”10”这种。唉不过不得不说，如果没有leetcode提示我哪些数据没通过，自己找实在是找不到啊..


int numDecodings(char* s) {
    int i = 0;
    int dp[1000] = {0};
    int len = strlen(s);
    if(s[0] == '0') return 0;
    dp[0] = 1;
    if((((s[0]-'0')*10+s[1]-'0')<=26) && len > 1 && s[1]!='0')
    {
        dp[1] = 2; // 可以组成两位数
    }
    else
    {
        if(s[0]>'2' && s[1] == '0') return 0;
        dp[1] = 1;
    }
    for(i=2;i<len;i++)
    {
        if(s[i] == '0')
        {
            if(s[i-1] == '1' || s[i-1] == '2')
            {
                dp[i] = dp[i-2];
            }
            else
            {
                return 0;
            }
        }
        else
        {
            if(s[i-1] == '1')
            {
                dp[i] = dp[i-1] + dp[i-2];
            }
            else if (s[i-1] == '2' && s[i]<='6')
            {
                dp[i] = dp[i-1] + dp[i-2];
            }
            else
            {
                dp[i] = dp[i-1];
            }
        }

    }
    return dp[strlen(s)-1];

}

打家劫舍(leetcode第198题)

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警.

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

也算是动态规划的一个经典题目。重要的状态转移方程如下第21行所示。简单解释一下。

由于当偷到第i个房子的时候，可以选择偷或者不偷(这里假设我们一次性的就求出所有的情况)，如果不偷，情况就和第i-1是一样的。但是如果偷了，就要在第i-2次的基础上相加。注意这里并没有舍弃i-1次的结果，他仍然有可能在下一次计算中被使用。因此可以写出状态转移方程为

$dp[i] = max(dp[i-1],dp[i-2]+nums[i])$

int max(int a,int b){
        return a > b ? a : b;
    }

int rob(int* nums, int numsSize){
    int i = 0;
    int dp[1000] = {0};
    dp[0] = nums[0];
    int MAX = nums[0];
    if(numsSize == 1)
    {
        return nums[0];
    }
    if(numsSize == 2) // 对于数组大小为1和2坐特殊处理
    {
        return max(nums[0],nums[1]);
    }
    dp[1] = max(nums[0],nums[1]);
    for(i=2;i<numsSize;i++)
    {
        dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
        if(dp[i]>MAX)
        {
            MAX = dp[i];
        }
    }
    return MAX;
}

删除并获得点数(leetcode第740题)

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-and-earn
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题初次做的时候没有什么思路。一开始想的是从第二个数字开始，找每次的最大值。在想状态转移方程里面转移的时候，该怎么删除之前已经加到sum中的数据，再新增一个计数空间复杂度就要翻倍。

但是实际上这道题是上面题目的变种。我们只需要一个简单的映射就可以把这道题划归到上面题目中。

如果我们建立一个由小到大排序的数组，数组下标就是数字，而数组内容就是数字重复的个数，这样就能很容易统计加上了多少数字。再想想，其实这个数组就是“如果取了a，那么a-1和a+1都需要丢弃”，那么也就是上面的打家劫舍题目。只不过现在的状态转移方程如下

$dp[i] = max(dp[i-1] , dp[i-2]+nums[i]*i)$


int max(int a ,int b )
{
    return a > b ? a : b;
}


int deleteAndEarn(int* nums, int numsSize){
    // first get the frequence case
    int fre[10010] = {0};
    int dp[10010] = {0};
    int i =0;
    int MAX = 0;
    for(i=0;i<numsSize;i++)
    {
        fre[nums[i]]++;
    }
    // dp
    dp[0] = 0;
    dp[1] = fre[1];
    for(i=2;i<10010;i++)
    {
        dp[i] = max(dp[i-1],dp[i-2]+fre[i]*i); // 使用转换后的fre数组，不再使用Num
        if(dp[i]>MAX)
        {
            MAX = dp[i];
        }
    }
    return MAX;
}

本文标题:dp

文章作者:

发布时间:2022-08-28, 15:40:01

最后更新:2022-09-14, 21:22:14

原始链接:https://nicholas-wei.github.io/2022/08/28/dp/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。