【算法小课堂】动态规划

桃扇骨 2024-02-05 23:04 41阅读 0赞

## 动态规划 ##

动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章，大多都是叙述概念，讲解原理，让人觉得晦涩难懂，即使一时间看懂了，发现当自己做题的时候又会觉得无所适从。我觉得，理解算法最重要的还是在于练习，只有通过自己练习，才可以更快地提升。话不多说，接下来，下面我就通过一个例子来一步一步讲解动态规划是怎样使用的，只有知道怎样使用，才能更好地理解，而不是一味地对概念和原理进行反复琢磨。

本题很明显

1.  状态表示dp【i】为第n个泰波那契数，![img][]
2.  编辑本题是第一种情况，后面的题目我们会不断遇到1，2，3的情况，我们后面再细讲
3.  而状态转移方程为题目也直接给了出来， Tn+3 = Tn + Tn+1 + Tn+2，状态转移方程： Tn = Tn -1+ Tn-2 + Tn-3
4.  初始化（防止越界的情况）：本题很明显Tn-3的时候当，n小于3的时候会出现越界的情况，因此我们要提前初始化好dp【0】 ，dp【1】，dp【2】
5.  填表顺序： 左到右![img][img 1]编辑
6.  返回值；dp【n】

细节问题：

*  当n<3的时候，就不需要进行Tn = Tn -1+ Tn-2 + Tn-3计算因此就可以直接返回

空间优化问题：

本题如果我们按照上面的写法的话，就需要开辟一个n+1大小的vector数组dp，当我们在计算第n个位置的时候，我们只需要n-1，n-2，n-3的位置，如果前面还有n-4和n-5都不需要的

![img][img 2]

因此我们就可以直接用三个变量a，b，c来优化，使得空间复杂度为o(1)

[面试题 08.01. 三步问题][08.01.]

分析一下题目的意思：

当从0号台阶到1号台阶，只有1种方法；

当从0号台阶到2号台阶，我们可以直接从0号台阶蹦到2号台阶，也可以从0-1-2，总共两种解法

当从0号台阶到3号台阶，我们可以从0号直接蹦到3号台阶，也可以0-1-2-3和0-2-3和0-1-3，总共4种解法

![img][img 3]编辑 眼尖的同学这个时候以及发现了状态转移方程了，我们注意一下（以到4号台阶为例)：我们可以看成从1号到4的方法数+2号到4号的方法数+3号到4号的方法数

1.  因此我们的状态表示dp【i】就表示到达第i号台阶的方法数
2.  状态转移方程：![img][img 4]编辑

此时有的同学会有一个疑问：就是我从i-2号台阶到i号台阶的时候不是有两种情况：

*  i-2到i
 *  i-2先到i-1再到i号台阶

其实不然：i-2先到i-1的这种情况以及是包含在i-1到i的方法数中

1.  初始化（防止越界的情况）：本题很明显Tn-3的时候当，n小于3的时候会出现越界的情况，因此我们要提前初始化好dp【0】 ，dp【1】，dp【2】
2.  填表顺序： 左到右
3.  返回值；dp【n】

### 解题思路： ###

> 本题的状态表示是通过经验+题目要求得出的
> 
> 状态表示：dp\[i\]代表以i位置结尾的所有解码方法总和
> 
> 状态转移方程：
> 
> ![img][img 5]编辑
> 
> 我们就观察以i位置结尾的数字串，此时有两种情况：
> 
>  *  s\[i\]单独解码
>  *  s\[i\]和s\[i-1\]一起解码
> 
> 先说s【i】单独解码的情况，当解码成功时，也就是s【i】代表的数字属于【1，9】，则dp【i】+=dp【i-1】，失败的话就是0了
> 
> 再来就是 s\[i\]和s\[i-1\]一起解码 的情况：当解码成功也就是这两个数字属于【10,26】,则dp【i】+=dp【i-2】，失败也是0
> 
> 初始化：dp【0】当s【0】属于1-9，dp【0】=1，s【0】=0的话dp【0】=0
> 
> dp【1】的话，此时就有两个数字，就分为两种情况，两个数字分开单独解码和两个数字一起解码，单独解码的话s【1】代表的数字属于【1，9】，dp【1】++，两个数字一起解码的话，当解码成功也就是这两个数字属于【10,26】,则dp【1】++
> 
> 填表顺序：从左导游
> 
> 返回值;dp\[n-1\]

### 解题代码： ###

class Solution {
        
    public:
        int numDecodings(string s) {
        
            int n = s.size();
            vector<int>dp(n + 1, 0);
            //初始化
            if (s[0] >= '1' && s[0] <= '9')dp[0] = 1;
            else dp[0] = 0;
            if (n == 1)return dp[0];
    
            if (dp[0] && s[1] - '0')dp[1]++;
            int num = (s[0] - '0') * 10 + (s[1] - '0');
            if (num >= 10 && num <= 26)dp[1]++;
    
            for (int i = 2; i < n; i++)
            {
        
                if (s[i] >= '1' && s[i] <= '9')dp[i] += dp[i - 1];
                num = (s[i - 1] - '0') * 10 + (s[i] - '0');
                if (num >= 10 && num <= 26)dp[i] += dp[i - 2];
            }
            return dp[n - 1];
        }
    };

![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传][20230724024159.png_origin_url_data_3Aimage_2Fgif_3Bbase64_2CR0lGODlhAQABAPABAP_2F_2F_2FwAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw_3D_3D_pos_id_img-LqFPPLZm-1704772749276]

[91. 解码方法][91.]

### 处理边界问题及初始化问题的的技巧： ###

我们可以给dp数组多开一个位置，也就是开n+1个空间，使整个数组向右移动一位

这样我们原本的dp【1】也可以移到循环中进行计算了！！！

![img][img 6]编辑

这里的0,1,2等都是下标

因此我们多出来一个位置0号下标的值是多少呢？

因为我们后面要计算dp【2】也就是原本的dp【1】的时候会运用到dp【i-2】和dp【i-1】

因为dp【i-1】不会出错，所以我们只需要注意dp【i-2】的正确性

当dp【2】时，也就是两位数字的解码方案数，当我们运用到dp【i-2】的时候，这个是两位数字一起解码，因此dp【i】+=dp【i-2】如果dp【0】为0，即使解码成功也等于没有解码成功，因此这里dp【0】要为1

### 优化后的代码： ###

class Solution {
        
    public:
        int numDecodings(string s) {
        
            int n=s.size();
            vector<int>dp(n+1);
            dp[0]=1;
            //初始化
            if(s[0]>='1'&&s[0]<='9')dp[1]=1;
            else dp[1]=0;
            if(n==1)return dp[1];
    
            /*if(dp[0]&&s[1]-'0')dp[1]++;
            int num=(s[0]-'0')*10+(s[1]-'0');
            if(num>=10&&num<=26)dp[1]++;*/
            
            for(int i=2;i<=n;i++)
            {
        
                if(s[i-1]>='1'&&s[i-1]<='9')dp[i]+=dp[i-1];
                int num=(s[i-2]-'0')*10+(s[i-1]-'0');
                if(num>=10&&num<=26)dp[i]+=dp[i-2];
            }
            return dp[n];
        }
    };

[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ba76921272184b57918c9e6559246265.png
[img 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/f12a4991499d4d47a9e204515ca0c654.png
[img 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/0a4e7d265ab9432c9daad30bfbaadc39.png
[08.01.]: https://leetcode.cn/problems/three-steps-problem-lcci/
[img 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/92346bd6c38e4a38a6174038a598e0a0.png
[img 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/e2b08dd694af4ed79697a2e994ccce1a.png
[img 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/3c06d75c0c5f4570b30216d5e9fed2fd.png
[20230724024159.png_origin_url_data_3Aimage_2Fgif_3Bbase64_2CR0lGODlhAQABAPABAP_2F_2F_2FwAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw_3D_3D_pos_id_img-LqFPPLZm-1704772749276]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ae3853a5c1cf431ea86fbe9904ec816d.png
[91.]: https://leetcode.cn/problems/decode-ways/
[img 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/4158bd7969d64d028fc874b6f065bf7e.png