可以使用动态规划来解决这个问题。首先，我们定义一个二维数组dp，dpi表示以第i个字符结尾的子串在形成矩阵时，最小的权值。

我们可以通过遍历字符串的每个字符来计算dp数组的值。对于第i个字符，我们需要考虑它与前面字符的连通性。如果第i个字符与前面字符相同，那么它可以与前面字符连通，此时dpi的值可以继承dpi-1的值。如果第i个字符与前面字符不同，那么它不能与前面字符连通，此时dpi的值需要在dpi-1的基础上加1。

具体的算法如下：

1. 读取输入的字符串长度n和字符串s。
2. 初始化一个二维数组dp，大小为n行n列，初始值都为无穷大。
3. 遍历字符串s的每个字符，记当前字符为s[i]。

4. 对于每个字符s[i]，遍历前面的字符s[j]，其中j从0到i-1。

   • 如果s[i]与s[j]相同，那么dpi = dpi-1。
   • 如果s[i]与s[j]不同，那么dpi = dpi-1 + 1。

5. 对于每个字符s[i]，遍历前面的字符s[j]，其中j从0到i-1。

   • 如果s[i]与s[j]相同，那么dpi = min(dpi, dpi)。
   • 如果s[i]与s[j]不同，那么dpi = min(dpi, dpi + 1)。
6. 输出dpn-1作为最小权值。

下面是Java代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = scanner.next();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
            for (int j = 0; j < i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + 1;
                }
                if (j > 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1]);
                }
            }
        }
        System.out.println(dp[n-1][n-1]);
    }
}

这个算法的时间复杂度为O(n^2)，其中n为字符串的长度。