アルゴリズム(LeetCode_面接問題46_数字を文字列に翻訳)

アルゴリズム#アルゴリズム#
概要:中程度の難易度の面接問題で、ダイナミックな計画内容に関連しています.それから私はできません.私はまた問題解を見ました(いつ私は自分でダイナミックな計画を学ぶことができますか).
タイトル
1つの数字を与えて、私達は以下の規則に従ってそれを文字列に訳します:0は“a”に訳して、1は“b”に訳して、......、11は“l”に訳して、......、25は“z”に訳します.1つの数字に複数の翻訳がある可能性があります.プログラミングして1つの関数を実現して、1つの数字がどれだけ異なる翻訳方法があるかを計算してください.出典:リベートリンク:面接問題46_数字を文字列に訳す
例
例1:
入力:12258出力:5解釈:12258は5種類の異なる翻訳があり、それぞれ「bccfi」、「bwfi」、「bczi」、「mcfi」と「mzi」である.
構想

聞かないで動的計画

この問題の動的計画の計画方程式について、現在読んでいる最後の点として点を取って、それからこの点を読んだ最大翻訳方法数を計算することができます.私たちは現在の点をiと呼びます.その前の点はi-1です.iを独立して翻訳すると、i点を読んだ最大翻訳方法数はi-1の最大翻訳方法数に等しくなります.i-1とiがつながって翻訳できる場合、私たちはそれをつなぎ合わせて翻訳すると、i点まで読む最大翻訳方法数はi-2の最大翻訳方法数に等しい.上記の2つの場合、i独立翻訳には条件はないが、i−1とiが一緒に翻訳するには、2つの和が10と25の間にあるべきであるという制限条件がある.独立した翻訳はいずれの条件でも成立することを明らかにした.すなわち、その最大翻訳方法数はi-1の最大翻訳方法数であり、その特殊な条件を満たすと、その最大翻訳方法数は保証の上にi-2の最大翻訳方法数を加えることができる.

方程式は、(25>=(10*i-1)+i>=10):f(i)=f(i-1)+f(i-2)の場合、f(i)=f(i)=f(i-1)

を表す.
Javaコード

public class Solution
{
    public int translateNum(int num) {
        int r [] = {0,1,1,0};         //    ，        ，        ，        
        int n = 1;
        while(num/n>=10)
        {
            n*=10;
        }
        while(n>0)
        {
            if((r[0]*10+num/n)>=10&&(r[0]*10+num/n)<=25)
            {
                r[3] = r[1]+r[2];
            }
            else
            {
                r[3] = r[2];
            }
            r[0] = num/n;
            num -= (num/n)*n;
            n/=10;
            r[1] = r[2];
            r[2] = r[3];
        }
        return r[3];
    }
}