牛客网 ==》腾讯2017暑期实习生编程题

题目：

链接：https://www.nowcoder.com/questionTerminal/28c1dc06bc9b4afd957b01acdf046e69
来源：牛客网
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

示例1

输入

abcda
google

输出

2
2


====》本文章主要是采用C#求解，
步骤：
1、先把输入的字符串进行反转，得到串1
2、利用动态规划求解两个字符串的最长公共子序列的长度
3、最后拿字符串的长度减去公共子序列的长度，得到的是需要删除的子串长度


得到的结果：======》在本地程序运行的结果什么都没问题，但是在把代码拷贝到牛客网上面以后，各种不通过。有时间还是要好好推敲一下。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace testNiuKe
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("请输入一串字符串：");
           string s = Console.ReadLine();
           
            Console.Write(RemoveHuiWen(s));//不能写WriteLine()===>换行时候字符串牛客网的输出用例显示错误！！！
            Console.ReadKey();
        }
        /// <summary>
        /// 判断一个字符串需要移除多少字符以后是回文
        /// </summary>
        private static int RemoveHuiWen(string s)
        {
            if (String.IsNullOrEmpty(s))
            {
                return 0;
            }
            string reverseS = null;//翻转字符串 abcda
            //反转字符串
            for (int i = s.Length - 1; i >= 0; i--)
            {
                reverseS += s[i];
            }
            int[][] c = new int[s.Length + 1][];
            for (int i = 0; i < s.Length + 1; i++)
            {
                c[i] = new int[reverseS.Length + 1];
            }

            for (int i = 1; i < s.Length; i++)
            {
                c[i][0] = 0;
            }
            for (int j = 1; j < reverseS.Length; j++)
            {
                c[0][j] = 0;
            }
            for (int i = 1; i < s.Length; i++)
            {
                for (int j = 1; j < reverseS.Length; j++)
                {
                    if (s[i] == reverseS[j])
                    {
                        c[i][j] = c[i - 1][j - 1] + 1;
                    }
                    else
                    {
                        c[i][j] = Math.Max(c[i - 1][j], c[i][j - 1]);
                    }
                }
            }


            return s.Length - c[s.Length - 1][reverseS.Length - 1]-1;
        }
    }
}