jiayuqicz 2020-02-02
一条包含字母 A-Z 的消息通过以下方式进行了编码:
‘A‘ -> 1
‘B‘ -> 2
...
‘Z‘ -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。
初思路:
一看到本题,我就想用回溯算法来递归,因为遇到 10<s[:2]<27的时候 就可以递归两条路径,一条是分开,一条是合并
但是递归方法时间复杂度高,存在大量的重复计算,比如 分开转化s[0],s[1] 与合并s[0:2],还是回到处理 s[2:]的路径上,所以我再去看看答案。
观后思路:
本题确实就是 爬楼梯问题,动态转移方程: dp[i] = dp[i-1] + dp[i-2] 但是多了一些限制条件
为什么是爬楼梯问题(动态规划)呢, 因为dp[i]一旦计算出来,就与之前过程再无关系。
收获:
1.状态转移方程很难写,不同情况对cur有不同的赋值:
11-19,21-26: cur = fitst + second
10,20 cur = first
出现0的情况还要分辨一下特殊情况,直接return0
下图转自,leetcode精选python答者 NFGC https://leetcode-cn.com/problems/decode-ways/solution/dong-tai-gui-hua-tu-jie-by-nfgc/
动态规划有时被称为递归的相反的技术。动态规划方案通常使用一个数组来建立一张表,用于存放被分解成众多子问题的解。当算法执行完毕,最终的解法将会在这个表中找到。今天我们先从我们最熟的斐波那契数列数列开始。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio&am