动态规划--状态转移_算法

解码方法

1.题目

2.思路

1）我们定义一个数组dp，其中dp[i]表示字符串s的前i个字符的解码方法总数。初始化时，dp[0]为1，因为空字符串有一种解码方式。dp[1]的值取决于第一个字符是否是'0'，如果不是'0'，则有一种解码方式，否则没有解码方式。

2）从第三个字符开始遍历字符串s（即i从2开始）。对于每个字符，我们考虑两种可能的解码方式：

单独解码最后一个字符：如果当前字符不是'0'，则它可以单独解码成一个字母。因此，我们可以将dp[i]增加dp[i-1]，因为这意味着我们保持之前的解码方式不变，并在末尾添加一个新的解码字符。
组合解码最后两个字符：我们检查最后两个字符组成的数字是否在10到26之间。如果是，这两个字符可以组合起来解码成一个字母。在这种情况下，我们可以将dp[i]增加dp[i-2]，因为这意味着我们不考虑最后一个字符，而是将最后两个字符作为一个整体进行解码，并加上之前的解码方式数。

在遍历完整个字符串后，dp[n]（其中n是字符串s的长度）将包含整个字符串的解码方法总数。

3.代码

import java.util.scanner;

public class jiema {
	//定义方法numdecodings,接收一个字符串s作为参数，返回解码方法的总数
	public int numdecodings(string s) {
		if(s==null || s.length()==0 || s.charat(0)=='0') {
			return 0;
		}
		
		//定义dp数组，dp[i]表示s的前i个字符的解码方法总数
		int n=s.length();
		int[] dp = new int[n+1];
		
		//空字符串有一种解码方式
		dp[0]=1;
		//第一个字符如果不是‘0’，则有一种解码方式，否则没有
		dp[1]=s.charat(0)!='0'?1:0;
		//从第二个字符开始遍历字符串s
		for(int i=2;i<=n;i++) {
			//情况1：单独解码最后一个字符
			//如果当前字符不是'0'，则可以单独解码成一个字母
			if(s.charat(i-1)!='0') {
				dp[i]+=dp[i-1];
			}
			
			//情况2：组合解码最后两个字符
			//取最后两个字符组成的数字
			int twodigit = integer.parseint(s.substring(i-2,i));
			
			//如果这个数字在10-26之间，则可以组合解码成一个字母
			if(twodigit >= 10&&twodigit <=26) {
				dp[i]+=dp[i-2];
			}
		}
		return dp[n];
		
	}
	
	public static void main(string[] args) {
		//创建对象
		jiema solution=new jiema();
		scanner scanner=new scanner(system.in);
		string s=scanner.nextline();
		scanner.close();
		//调用numdecodings方法
		int result = solution.numdecodings(s);
		system.out.println(result);
		
	}
}

4.知识

1）s.charat(0)

在java中，s.charat(0) 是一个方法调用，用于获取字符串 s 中位于索引 0 的字符。在java中，字符串是字符的序列，并且索引是从 0 开始的。因此，s.charat(0) 会返回字符串 s 的第一个字符。

例如，如果有一个字符串 s = "hello"，那么 s.charat(0) 将返回字符 'h'。

这里是 s.charat(0) 的一些要点：

如果字符串 s 是空的（即 s.length() == 0），那么调用 s.charat(0) 会抛出一个 stringindexoutofboundsexception，因为索引 0 不存在。
如果 s 是 null，那么调用 s.charat(0) 将会抛出一个 nullpointerexception，因为你不能在 null 对象上调用方法。

因此，在调用 s.charat(0) 之前，通常最好检查字符串 s 是否为空或 null，以避免这些异常。

2）int twodigit = integer.parseint(s.substring(i-2,i));

integer.parseint() 方法用于将字符串参数作为有符号的十进制整数进行解析。如果字符串参数以有效的十进制数字序列开始，则该方法将返回该序列表示的整数。

在代码 int twodigit = integer.parseint(s.substring(i-2, i)); 中，s.substring(i-2, i) 创建了一个从字符串 s 的 i-2 位置开始（包含）到 i 位置结束（不包含）的子字符串。这个子字符串包含了 s 的最后两个字符。

3）   scanner scanner=new scanner(system.in);
       string s=scanner.nextline();
       scanner.close();

从键盘获取字符串的代码，导入包import java.util.scanner;