动态规划之解码方法｜Go主题月

概述【Golang主题学习月】周末肝了几道动态规划题，发了一个超细腻的教学版，反响很不错哦，接下来我会使用两种语言进行编码刷题，分别是GO和JAVA，各位菁英们，坚持刷题吧。????如果你对动态规划不熟悉，望转到该篇 \color{red}{如果你对动态规划不熟悉，望转到该篇~}如果你对动态规划不熟悉，望

【Golang主题学习月】周末肝了几道动态规划题，发了一个超细腻的教学版，反响很不错哦，接下来我会使用两种语言进行编码刷题，分别是GO和JAVA，各位菁英们，坚持刷题吧。

????

如果你对动态规划不熟悉，望转到该篇 \color{red}{如果你对动态规划不熟悉，望转到该篇~}如果你对动态规划不熟悉，望转到该篇 

肝了好多天-动态规划十连-超细腻解析｜刷题打卡

什么题可以选择动态规划来做？

1.计数

有多少种方式走到右下角有多少种方法选出k个数是的和是sum

2.求最大值最小值

从左上角走到右下角路径的最大数字和最长上升子序列长度

3.求存在性

取石子游戏,先手是否必胜能不能选出k个数使得和是sum@H_404_44@leecode 91. 解码方法

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

'A' -> 1

'B' -> 2

...

'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。

例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。

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

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

 

示例 1：

输入：s = "12"输出：2解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"输出：3解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "0"输出：0解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例 4：

输入：s = "06"输出：0解释："06" 不能映射到 "F" ，因为字符串开头的 0 无法指向一个有效的字符。  

提示：

1 <= s.length <= 100s 只包含数字，并且可能包含前导零。

---

--

动态规划四步走~~~ 其实这道题主要考虑一下边界>6的数字 = 0的数字就可以pass了。❤️❤️❤️❤️

2.1. 动态规划组成部分1：确定状态

简单的说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，类似数学题中x, y, z代表什么

2.2. 动态规划组成部分3：初始条件和边界情况

初始条件：

以0开头或者以0结尾除了10、20其他数字都不满足。

详情见代码~~

2.3. 动态规划组成部分4：计算顺序

依次

参考代码

GO语言版

 func numDeCodings(s string) int {    n := len(s)    if n == 0 {        return 0    }    dp := make([]int, n+1)    dp[0] = 1    if s[0] == '0' {        dp[1] = 0    } else {        dp[1] = 1    }    for i := 1; i < n; i++ {        if s[i-1] == '1' || (s[i-1] == '2' && s[i] < '7') {            //如果是20、10            if(s[i] == '0') {                dp[i + 1] = dp[i - 1]            } else { // //如果是11-19、21-26                dp[i + 1] = dp[i] + dp[i - 1]            }        } else if(s[i] == '0'){            //如果是0、30、40、50            return 0        } else {             //i-1和i无法构成一个字母             dp[i + 1] = dp[i]        }        }     return dp[n]}复制代码

JAVA版

  public int numDeCodings(String s) {        int n = s.length();        if(n == 0) return 0;        int[] dp = new int[n + 1];        dp[0] = 1;        dp[1] = s.charat(0) == '0' ? 0 : 1;        for(int i = 1; i < n; i++){            if(s.charat(i-1) == '1' || s.charat(i-1) == '2' && s.charat(i) <'7'){                //如果是20、10                if(s.charat(i) == '0') dp[i + 1] = dp[i - 1];                    //如果是11-19、21-26                else dp[i + 1] = dp[i] + dp[i - 1];            }else if(s.charat(i) == '0'){                //如果是0、30、40、50                return 0;            }else{                //i-1和i无法构成一个字母                dp[i + 1] = dp[i];            }        }        return dp[n];    }    @Test    public voID isnumDeCodings() {        int i = numDeCodings("100");        Assert.assertNotNull(i);    }    复制代码

❤️❤️❤️❤️

非常感谢人才们能看到这里，如果这个文章写得还不错，觉得有点东西的话 求点赞???? 求关注❤️ 求分享???? 对帅气欧巴的我来说真的 非常有用！！！

如果本篇博客有任何错误，请批评指教，不胜感激 ！

文末福利，最近整理一份面试资料《Java面试通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式：GitHub github.com/Tingyu-Note…，更多内容关注公号：汀雨笔记，陆续奉上。

总结

以上是内存溢出为你收集整理的动态规划之解码方法｜Go主题月全部内容，希望文章能够帮你解决动态规划之解码方法｜Go主题月所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。